Find the Only Non Repeating Element Using XOR in DSA C

Mental Model

XORing a number with itself cancels out to zero, so XORing all numbers leaves only the one that appears once.

Analogy: Imagine you have pairs of socks in a drawer, and one sock without a pair. If you match and remove pairs, the leftover sock is the one without a pair.

Array: [2] -> [3] -> [2] -> [4] -> [3] -> null
XOR process: 0 ⊕ 2 ⊕ 3 ⊕ 2 ⊕ 4 ⊕ 3 = 4 (leftover)

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3]

Goal: Find the single number that does not repeat in the array

Step 1: Start with result = 0, XOR with first element 2

result = 0 ⊕ 2 = 2

Why: Initialize result to zero and combine with first number

Step 2: XOR result with second element 3

result = 2 ⊕ 3 = 1

Why: Combine next number to cancel duplicates later

Step 3: XOR result with third element 2

result = 1 ⊕ 2 = 3

Why: XOR with duplicate 2 cancels one 2 out

Step 4: XOR result with fourth element 4

result = 3 ⊕ 4 = 7

Why: Add next number to result

Step 5: XOR result with fifth element 3

result = 7 ⊕ 3 = 4

Why: XOR with duplicate 3 cancels one 3 out

Result:

Final result = 4, which is the only non-repeating element

Annotated Code

DSA C

#include <stdio.h>

int findNonRepeating(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result ^= arr[i]; // XOR current element with result
    }
    return result; // result holds the non-repeating element
}

int main() {
    int arr[] = {2, 3, 2, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int nonRepeating = findNonRepeating(arr, n);
    printf("%d\n", nonRepeating);
    return 0;
}

result ^= arr[i]; // XOR current element with result

XOR each element to cancel duplicates and keep only unique

return result; // result holds the non-repeating element

Return the leftover number after all XOR operations

Output

4

Complexity Analysis

Time: O(n) because we traverse the array once to XOR all elements

Space: O(1) because only one variable is used regardless of input size

vs Alternative: Better than using hash maps which require O(n) space; XOR uses constant space

Edge Cases

Array with only one element

Returns that element as it is the only one

DSA C

for (int i = 0; i < n; i++) { result ^= arr[i]; }

Array where all elements except one appear twice

Correctly returns the single non-repeating element

DSA C

result ^= arr[i];

When to Use This Pattern

When you see a problem asking for the single unique element among duplicates, use XOR to cancel pairs efficiently.

Common Mistakes

Mistake: Not initializing result to zero before XORing
Fix: Initialize result = 0 to ensure correct XOR accumulation

Mistake: Using addition or subtraction instead of XOR
Fix: Use XOR operator (^) because it cancels duplicates correctly

Summary

Finds the single non-repeating element in an array where all others repeat twice.

Use when you need to find one unique number among pairs efficiently.

XORing duplicates cancels them out, leaving only the unique number.

Practice

1. What does the XOR operation help find in an array where every element except one repeats exactly twice?

easy

A. The smallest element

B. The sum of all elements

C. The largest element

D. The only element that does not repeat

Solution

1. Step 1: Understand XOR properties

   XOR of a number with itself is 0, and XOR with 0 is the number itself.

2. Step 2: Apply XOR on all elements

   XORing all elements cancels out duplicates, leaving only the unique element.

3. Final Answer:

   The only element that does not repeat -> Option D

4. Quick Check:

   XOR cancels duplicates = unique element [OK]

Hint: XOR all elements; duplicates vanish, unique remains [OK]

Common Mistakes:

• Thinking XOR sums elements
• Assuming XOR finds max or min
• Confusing XOR with addition

2. Which of the following is the correct syntax to XOR two integers a and b in C?

easy

A. a | b

B. a & b

C. a ^ b

D. a + b

Solution

1. Step 1: Identify XOR operator in C

   The caret symbol (^) is the XOR operator in C.

2. Step 2: Confirm correct usage

   Using a ^ b performs bitwise XOR between integers a and b.

3. Final Answer:

   a ^ b -> Option C

4. Quick Check:

   ^ is XOR operator in C [OK]

Hint: Use ^ for XOR in C, not & or | [OK]

Common Mistakes:

• Using & instead of ^
• Using | instead of ^
• Using + instead of ^

3. What is the output of the following C code?

int arr[] = {2, 3, 5, 4, 5, 3, 4};
int result = 0;
for(int i = 0; i < 7; i++) {
    result ^= arr[i];
}
printf("%d", result);

medium

A. 2

B. 5

C. 3

D. 4

Solution

1. Step 1: XOR all elements in the array

   Calculate XOR stepwise: 0^2=2, 2^3=1, 1^5=4, 4^4=0, 0^5=5, 5^3=6, 6^4=2.

2. Step 2: Final XOR result is 2

   After XORing all elements, duplicates cancel out, leaving 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   XOR cancels duplicates = 2 [OK]

Hint: XOR all; duplicates vanish, unique stays [OK]

Common Mistakes:

• Not XORing all elements
• Miscomputing XOR steps
• Assuming sum or max instead

4. Identify the error in this C code snippet that tries to find the unique element using XOR:

int arr[] = {1, 2, 1, 3, 2};
int result = arr[0];
for(int i = 1; i <= 5; i++) {
    result ^= arr[i];
}
printf("%d", result);

medium

A. Loop condition should be < 5, not <= 5

B. Initialize result to 0 instead of arr[0]

C. Use & operator instead of ^

D. Array size is incorrect

Solution

1. Step 1: Check loop bounds

   Array has 5 elements indexed 0 to 4; loop runs i from 1 to 5 inclusive, causing out-of-bounds access at i=5.

2. Step 2: Correct loop condition

   Change loop to i < 5 to avoid accessing arr[5] which is invalid.

3. Final Answer:

   Loop condition should be < 5, not <= 5 -> Option A

4. Quick Check:

   Array index out of bounds fixed by i < 5 [OK]

Hint: Loop till i < array size, not <= [OK]

Common Mistakes:

• Using <= instead of < in loop
• Ignoring array bounds
• Wrong operator used

5. Given an array where every element repeats twice except one element which repeats thrice, can XOR alone find the unique element? If not, what is the correct approach?

hard

A. Yes; XOR works for any repetition count

B. No; use bit counting and modulo 3 to find the unique element

C. No; use sum of elements minus sum of unique elements

D. Yes; XOR twice and then XOR thrice elements

Solution

1. Step 1: Understand XOR limitation

   XOR works only when duplicates appear exactly twice; it fails if duplicates appear thrice.

2. Step 2: Use bit counting method

   Count bits in all numbers, take modulo 3 of each bit count to isolate the unique element's bits.

3. Final Answer:

   No; use bit counting and modulo 3 to find the unique element -> Option B

4. Quick Check:

   XOR fails if duplicates appear thrice; bit count works [OK]

Hint: XOR only works for duplicates twice; use bit count mod 3 otherwise [OK]

Common Mistakes:

• Assuming XOR works for any duplicate count
• Trying to XOR thrice duplicates
• Ignoring bit counting approach