Two Non Repeating Elements in Array Using XOR in DSA C

Mental Model

Use XOR to cancel out pairs and isolate two unique numbers by splitting based on a differing bit.

Analogy: Imagine you have a box of socks where every sock has a matching pair except two unique socks. By shaking the box and separating socks by a small difference, you can find those two unique socks without checking each one twice.

Array: [2, 3, 7, 9, 2, 3]
XOR all: 14 (binary 1110)
Find rightmost set bit in 14: 2 (binary 0010)
Split array by this bit:
Group 1 (bit set): 3, 7, 9, 3 -> XOR = 7
Group 2 (bit not set): 2, 2 -> XOR = 9
XOR each group separately to find unique elements.

Dry Run Walkthrough

Input: array: [2, 3, 7, 9, 2, 3]

Goal: Find the two numbers that appear only once (7 and 9) using XOR operations.

Step 1: XOR all elements to get xor_all

2 ⊕ 3 ⊕ 7 ⊕ 9 ⊕ 2 ⊕ 3 = 14 (binary 1110)

Why: XOR cancels pairs, leaving XOR of two unique numbers.

Step 2: Find rightmost set bit in xor_all

rightmost set bit mask = 2 (binary 0010)

Why: This bit differs between the two unique numbers.

Step 3: Divide array into two groups based on this bit and XOR each group

Group 1 (bit set): 3, 7, 9, 3 -> XOR = 7
Group 2 (bit not set): 2, 2 -> XOR = 9

Why: Pairs cancel out in each group, leaving one unique number per group.

Step 4: The XOR results from the groups are the unique numbers

unique1 = 7, unique2 = 9

Why: We XOR group 1 and group 2 results separately to get unique numbers.

Step 5: Correct approach: XOR elements with bit set to get unique1, XOR elements without bit set to get unique2

unique1 = 7, unique2 = 9

Why: Separating elements by bit isolates each unique number.

Result:

7 -> 9 -> null (the two unique numbers found)

Annotated Code

DSA C

#include <stdio.h>

void findTwoUnique(int arr[], int n, int *x, int *y) {
    int xor_all = 0;
    for (int i = 0; i < n; i++) {
        xor_all ^= arr[i];
    }

    int set_bit = xor_all & (-xor_all); // rightmost set bit

    *x = 0;
    *y = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] & set_bit) {
            *x ^= arr[i];
        } else {
            *y ^= arr[i];
        }
    }
}

int main() {
    int arr[] = {2, 3, 7, 9, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x, y;
    findTwoUnique(arr, n, &x, &y);
    printf("%d -> %d -> null\n", x, y);
    return 0;
}

xor_all ^= arr[i];

XOR all elements to cancel pairs and get XOR of two unique numbers

int set_bit = xor_all & (-xor_all);

Find rightmost set bit to differentiate two unique numbers

if (arr[i] & set_bit) { *x ^= arr[i]; } else { *y ^= arr[i]; }

Divide elements into two groups by set bit and XOR separately to isolate unique numbers

Output

7 -> 9 -> null

Complexity Analysis

Time: O(n) because we traverse the array twice: once to XOR all elements and once to separate groups.

Space: O(1) because we use only a few variables regardless of input size.

vs Alternative: Compared to using hash maps which require O(n) space, this XOR method uses constant space and is faster.

Edge Cases

Array with only two elements which are unique

The function returns those two elements correctly.

DSA C

xor_all ^= arr[i];

Array where unique elements are at the start or end

The function still finds the unique elements correctly.

DSA C

if (arr[i] & set_bit) { *x ^= arr[i]; } else { *y ^= arr[i]; }

Array with duplicates but only two unique elements

Duplicates cancel out, unique elements are found.

DSA C

xor_all ^= arr[i];

When to Use This Pattern

When you see a problem asking to find two unique numbers in an array where others appear twice, reach for the XOR splitting pattern because it efficiently isolates unique elements without extra space.

Common Mistakes

Mistake: Not finding the rightmost set bit correctly, leading to wrong grouping.
Fix: Use 'set_bit = xor_all & (-xor_all)' to isolate the rightmost set bit.

Mistake: XORing all elements into one variable and returning it directly.
Fix: Remember XOR of two unique numbers is not the answer; split array by set bit and XOR groups separately.

Summary

Finds two unique numbers in an array where all others appear twice using XOR.

Use when you need to find exactly two non-repeating elements efficiently without extra space.

The key insight is to use XOR to cancel pairs and split elements by a differing bit to isolate unique numbers.