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 the array into two groups based on a set bit.

Analogy: Imagine you have pairs of socks mixed in a pile, except two socks are unique. By shaking the pile and separating socks by a unique feature (like color), you can find the two unmatched socks.

Array: [2, 3, 7, 9, 2, 3]
XOR all: 2 ⊕ 3 ⊕ 7 ⊕ 9 ⊕ 2 ⊕ 3 = 7 ⊕ 9 = 14 (binary 1110)
Split by rightmost set bit (bit 1):
Group 1: elements with bit 1 set -> 2, 3, 7, 2, 3
Group 2: elements with bit 1 not set -> 9
XOR Group1: 2⊕3⊕7⊕2⊕3 = 7
XOR Group2: 9
Result: unique elements are 7 and 9

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

xor_all = 7 ⊕ 9 = 14 (binary 1110)

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

Step 2: Find rightmost set bit in xor_all (14) -> set_bit = 2 (binary 0010)

set_bit = 2

Why: This bit differs between the two unique numbers, used to separate them

Step 3: Divide elements into two groups based on set_bit: group1 with bit set, group2 without

group1: 2, 3, 7, 2, 3; group2: 9

Why: Unique numbers fall into different groups

Step 4: XOR all elements in group1 -> result1 = 2 ⊕ 3 ⊕ 7 ⊕ 2 ⊕ 3 = 7

result1 = 7

Why: Pairs cancel out, leaving the unique number in this group

Step 5: XOR all elements in group2 -> result2 = 9

result2 = 9

Why: XOR of unique number in this group (no pairs)

Step 6: The two results are the unique numbers

unique elements: 7 and 9

Why: These are the two non-repeating elements

Result:

Unique elements: 7 and 9

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> findTwoUnique(const vector<int>& arr) {
    int xor_all = 0;
    // XOR all elements to get xor of two unique numbers
    for (int num : arr) {
        xor_all ^= num;
    }

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

    int num1 = 0, num2 = 0;
    // Divide elements into two groups and XOR separately
    for (int num : arr) {
        if (num & set_bit) {
            num1 ^= num; // group with set bit
        } else {
            num2 ^= num; // group without set bit
        }
    }

    return {num1, num2};
}

int main() {
    vector<int> arr = {2, 3, 7, 9, 2, 3};
    pair<int, int> result = findTwoUnique(arr);
    cout << result.first << " " << result.second << "\n";
    return 0;
}

for (int num : arr) { xor_all ^= num; }

XOR all elements to isolate XOR of two unique numbers

int set_bit = xor_all & (-xor_all);

Find rightmost set bit to separate two unique numbers

for (int num : arr) { if (num & set_bit) { num1 ^= num; } else { num2 ^= num; } }

Divide elements into two groups and XOR separately to find unique numbers

Output

7 9

Complexity Analysis

Time: O(n) because we traverse the array a constant number of times

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

vs Alternative: Naive approach uses extra space like hash maps with O(n) space, this uses XOR to achieve O(1) space

Edge Cases

Array with only two elements which are unique

Returns those two elements directly

DSA C++

for (int num : arr) { xor_all ^= num; }

Array where unique elements are adjacent

Algorithm still correctly separates and finds unique elements

DSA C++

for (int num : arr) { if (num & set_bit) { num1 ^= num; } else { num2 ^= num; } }

Array with multiple pairs and two unique elements

Pairs cancel out correctly, unique elements isolated

DSA C++

for (int num : arr) { xor_all ^= num; }

When to Use This Pattern

When you see a problem asking to find two unique numbers among pairs, reach for the XOR splitting pattern because it efficiently isolates them without extra space.

Common Mistakes

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

Mistake: XORing all elements in one group only, missing the other unique number
Fix: Divide elements into two groups based on set bit and XOR both 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 among pairs efficiently.

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

Practice

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

easy

A. XOR counts the frequency of each element

B. XOR sorts the array to separate unique elements

C. XOR of all elements gives XOR of the two unique elements

D. XOR swaps the two unique elements in the array

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 to all elements

   XORing all elements cancels out repeating elements, leaving XOR of two unique elements.

3. Final Answer:

   XOR of all elements gives XOR of the two unique elements -> Option C

4. Quick Check:

   XOR cancels duplicates, leaving unique pair XOR [OK]

Hint: XOR all elements to isolate unique pair XOR result [OK]

Common Mistakes:

• Thinking XOR sorts or counts elements
• Assuming XOR gives unique elements directly
• Confusing XOR with addition or subtraction

2. Which of the following C++ code snippets correctly initializes the XOR variable to find two unique elements in an array arr of size n?

easy

A. int xorVal = 0; for(int i = 1; i <= n; i++) xorVal ^= arr[i];

B. int xorVal = 0; for(int i = 0; i < n; i++) xorVal ^= arr[i];

C. int xorVal = 1; for(int i = 0; i < n; i++) xorVal ^= arr[i];

D. int xorVal = arr[0]; for(int i = 1; i < n; i++) xorVal += arr[i];

Solution

1. Step 1: Initialize XOR with 0

   Start with 0 because XOR with 0 returns the number itself.

2. Step 2: Loop through array correctly

   Loop from 0 to n-1 to cover all elements; use XOR assignment operator ^=.

3. Final Answer:

   int xorVal = 0; for(int i = 0; i < n; i++) xorVal ^= arr[i]; -> Option B

4. Quick Check:

   Correct loop and XOR initialization [OK]

Hint: Initialize XOR with 0 and loop from 0 to n-1 [OK]

Common Mistakes:

• Starting loop from 1 and missing first element
• Using addition instead of XOR
• Initializing XOR with 1 instead of 0
• Looping out of array bounds

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

int arr[] = {2, 3, 7, 9, 2, 3};
int n = 6;
int xorVal = 0;
for(int i = 0; i < n; i++) {
    xorVal ^= arr[i];
}
std::cout << xorVal << std::endl;

medium

A. 14

B. 9

C. 7

D. 0

Solution

1. Step 1: XOR all elements

   Calculate XOR stepwise: 0^2=2, 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Result is XOR of two unique elements

   Since 2 and 3 repeat, XOR leaves 7 and 9 combined as 14.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   XOR of unique pair (7^9) = 14 [OK]

Hint: XOR duplicates cancel; result is XOR of unique elements [OK]

Common Mistakes:

• Calculating XOR incorrectly stepwise
• Assuming output is one unique element
• Confusing XOR with sum

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

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

medium

A. Loop runs out of array bounds causing runtime error

B. XOR operator is used incorrectly

C. xorVal should be initialized with arr[0]

D. Loop should start from 1 instead of 0

Solution

1. Step 1: Check loop bounds

   Loop runs from i=0 to i<=n, which means i goes up to n, exceeding array index (0 to n-1).

2. Step 2: Consequence of out-of-bounds access

   Accessing arr[n] causes undefined behavior or runtime error.

3. Final Answer:

   Loop runs out of array bounds causing runtime error -> Option A

4. Quick Check:

   Array index must be less than n [OK]

Hint: Use i < n in loops to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing xorVal incorrectly
• Starting loop from wrong index

5. Given the array arr = {4, 1, 2, 1, 2, 5}, which of the following steps correctly finds the two non-repeating elements using XOR?

hard

A. Add all elements and subtract twice the sum of repeating elements

B. Sort array, then pick first two elements as unique

C. XOR all elements to get 1, then XOR with 0 to get unique elements

D. XOR all elements to get 1, find rightmost set bit, partition array by this bit, XOR partitions separately

Solution

1. Step 1: XOR all elements

   XOR(4^1^2^1^2^5) = 4 ^ (1^1) ^ (2^2) ^ 5 = 4 ^ 0 ^ 0 ^ 5 = 1.

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

   Rightmost set bit of 1 is 1 (binary 0001).

3. Step 3: Partition array by this bit and XOR separately

   Group elements with this bit set and not set, XOR each group to find unique elements 4 and 5.

4. Final Answer:

   XOR all elements to get 1, find rightmost set bit, partition array by this bit, XOR partitions separately -> Option D

5. Quick Check:

   Partitioning by set bit isolates unique elements [OK]

Hint: Use rightmost set bit to split and XOR partitions [OK]

Common Mistakes:

• Skipping partition step after XOR
• Using sorting instead of XOR
• Confusing addition with XOR