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.