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.

Practice

1. What is the main purpose of using XOR operation to find two non-repeating elements in an array where every other element repeats twice?

easy

A. To cancel out all repeating elements and isolate the XOR of the two unique elements

B. To sort the array in ascending order

C. To count the frequency of each element

D. To reverse the array elements

Solution

1. Step 1: Understand XOR property for duplicates

   XOR of two identical numbers is 0, so XORing all elements cancels out duplicates.

2. Step 2: Result after XORing all elements

   The result is XOR of the two unique elements because duplicates cancel out.

3. Final Answer:

   To cancel out all repeating elements and isolate the XOR of the two unique elements -> Option A

4. Quick Check:

   XOR cancels duplicates = isolate unique elements [OK]

Hint: XOR duplicates become zero, leaving unique elements XOR [OK]

Common Mistakes:

• Thinking XOR sorts the array
• Using XOR to count frequencies
• Assuming XOR reverses elements

2. Which of the following C code snippets correctly initializes the XOR variable to start finding two non-repeating elements?

easy

A. int xor = 1;

B. int xor = 0;

C. int xor = -1;

D. int xor = NULL;

Solution

1. Step 1: Understand XOR identity element

   XOR with 0 leaves the number unchanged, so start with 0.

2. Step 2: Initialize XOR variable

   Setting xor = 0 allows XORing all elements correctly.

3. Final Answer:

   int xor = 0; -> Option B

4. Quick Check:

   Start XOR with 0 for correct accumulation [OK]

Hint: Initialize XOR with 0 because 0 XOR x = x [OK]

Common Mistakes:

• Initializing XOR with 1 or -1
• Using NULL for integer variable
• Not initializing XOR variable

3. What will be the output of the following C code snippet?

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

medium

A. 14

B. 9

C. 7

D. 0

Solution

1. Step 1: XOR all elements in the array

   Calculate 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Result after XORing all elements

   The final XOR value is 14, which is XOR of the two unique elements 7 and 9.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   XOR all elements = 14 [OK]

Hint: XOR all elements to get XOR of unique pair [OK]

Common Mistakes:

• Stopping XOR early
• Miscomputing XOR values
• Assuming output is one unique element

4. Identify the error in the following code snippet that attempts to find two non-repeating elements using XOR:

int arr[] = {4, 1, 2, 1, 2, 5};
int xor = 0;
for(int i = 0; i < 6; i++) {
    xor ^= arr[i];
}
int set_bit = xor & ~(xor - 1);
int x = 0, y = 0;
for(int i = 0; i < 6; i++) {
    if(arr[i] & set_bit)
        x ^= arr[i];
    else
        y ^= arr[i];
}
printf("%d %d", x, y);

medium

A. Incorrect calculation of set_bit using xor & ~(xor - 1)

B. Loop range should be 0 to 5, not 0 to 6

C. Missing initialization of x and y to zero

D. No error, code works correctly

Solution

1. Step 1: Check set_bit calculation

   set_bit = xor & ~(xor - 1) correctly finds rightmost set bit.

2. Step 2: Verify loops and initialization

   Loops run from 0 to 5 (6 elements), x and y initialized to 0 correctly.

3. Final Answer:

   No error, code works correctly -> Option D

4. Quick Check:

   Code logic and syntax are correct [OK]

Hint: Check bitwise operations and loop ranges carefully [OK]

Common Mistakes:

• Miscomputing set_bit
• Wrong loop boundaries
• Uninitialized variables

5. Given an array where exactly two elements appear once and all others appear twice, how can you find those two unique elements efficiently using XOR? Choose the correct sequence of steps.

hard

A. Sort the array, then scan to find unique elements

B. Use a hash map to count frequencies, then pick elements with count 1

C. XOR all elements, find rightmost set bit in XOR result, divide elements into two groups by that bit, XOR each group separately

D. XOR all elements twice to get unique elements

Solution

1. Step 1: XOR all elements to get XOR of two unique elements

   This cancels out duplicates and leaves XOR of unique pair.

2. Step 2: Find rightmost set bit in XOR result

   This bit differs between the two unique elements.

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

   This separates the two unique elements and finds them individually.

4. Final Answer:

   XOR all elements, find rightmost set bit in XOR result, divide elements into two groups by that bit, XOR each group separately -> Option C

5. Quick Check:

   Use XOR and bit partitioning to find unique elements [OK]

Hint: Use XOR and bit mask to split and find unique elements [OK]

Common Mistakes:

• Sorting instead of XOR
• Using hash map (extra space)
• XORing twice without grouping