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. If you take out all socks and pair them up, only the single unmatched sock remains alone.

Array: [2, 3, 2, 4, 3]
XOR process: 2 ⊕ 3 ⊕ 2 ⊕ 4 ⊕ 3 = 4

Dry Run Walkthrough

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

Goal: Find the element that appears only once in the array

Step 1: XOR result starts at 0, XOR with 2

result = 0 ⊕ 2 = 2

Why: Start with zero because XOR with zero returns the number itself

Step 2: XOR result with 3

result = 2 ⊕ 3 = 1

Why: XOR combines bits, keeps track of unique bits so far

Step 3: XOR result with 2 again

result = 1 ⊕ 2 = 3

Why: XORing with 2 again cancels previous 2, leaving unique bits

Step 4: XOR result with 4

result = 3 ⊕ 4 = 7

Why: Add new unique number bits

Step 5: XOR result with 3 again

result = 7 ⊕ 3 = 4

Why: XORing with 3 again cancels previous 3, leaving only 4

Result:

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

Annotated Code

DSA C++

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

int findNonRepeating(const vector<int>& nums) {
    int result = 0; // start with zero
    for (int num : nums) {
        result ^= num; // XOR accumulates unique bits
    }
    return result; // leftover is the unique element
}

int main() {
    vector<int> nums = {2, 3, 2, 4, 3};
    int unique = findNonRepeating(nums);
    cout << unique << "\n";
    return 0;
}

int result = 0; // start with zero

initialize XOR accumulator to zero

for (int num : nums) { result ^= num; }

XOR each number to cancel duplicates and keep unique

return result;

return the only non-repeating element

Output

4

Complexity Analysis

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

Space: O(1) because we use only one variable to store XOR result

vs Alternative: Compared to using a hash map to count frequencies (O(n) time and O(n) space), XOR uses less memory and is faster

Edge Cases

array with only one element

returns that element as it is the only one

DSA C++

int result = 0; // start with zero

array where all elements except one appear twice

correctly returns the single unique element

DSA C++

result ^= num; // XOR accumulates unique bits

empty array

returns 0 as no elements to XOR

DSA C++

int result = 0; // start with zero

When to Use This Pattern

When you see a problem asking for the single unique element among duplicates, reach for the XOR pattern because it cancels pairs efficiently.

Common Mistakes

Mistake: Starting XOR accumulator with a non-zero value
Fix: Always initialize XOR accumulator to zero to avoid incorrect results

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

Summary

Finds the only element that does not repeat by XORing all elements.

Use when all elements except one appear exactly twice.

XORing duplicates cancels them out, leaving the unique element.

Practice

1. What does the XOR operation do when applied between two identical numbers?

easy

A. It returns 0

B. It returns the number itself

C. It returns 1

D. It returns the sum of the numbers

Solution

1. Step 1: Understand XOR property for identical numbers

   XOR of a number with itself always results in 0 because bits cancel out.

2. Step 2: Apply XOR to example

   For example, 5 XOR 5 = 0.

3. Final Answer:

   It returns 0 -> Option A

4. Quick Check:

   X XOR X = 0 [OK]

Hint: XOR of same numbers is always zero [OK]

Common Mistakes:

• Thinking XOR returns the number itself
• Confusing XOR with OR or AND
• Assuming XOR returns 1 for identical numbers

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

easy

A. int result = a && b;

B. int result = a ^ b;

C. int result = a | b;

D. int result = a & b;

Solution

1. Step 1: Identify XOR operator in C++

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

2. Step 2: Check syntax correctness

   Using int result = a ^ b; correctly computes XOR of a and b.

3. Final Answer:

   int result = a ^ b; -> Option B

4. Quick Check:

   Use ^ for XOR in C++ [OK]

Hint: Use ^ symbol for XOR in C++ [OK]

Common Mistakes:

• Using && instead of ^ for XOR
• Using | or & which are OR and AND
• Missing semicolon at end

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];
}
std::cout << result << std::endl;

medium

A. 2

B. 0

C. 5

D. 4

Solution

1. Step 1: XOR all elements in the array

   Perform 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: Identify the non-repeating element

   All repeating elements cancel out, leaving 2 as the only non-repeating element.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Only non-repeating element = 2 [OK]

Hint: XOR all elements; result is unique number [OK]

Common Mistakes:

• Not XORing all elements correctly
• Confusing output with a repeating element
• Assuming sum instead of XOR

4. Identify the error in the following code snippet that tries to find the only non-repeating element using XOR:

int arr[] = {1, 2, 1, 3, 2};
int result;
for(int i = 0; i < 5; i++) {
    result ^= arr[i];
}
std::cout << result << std::endl;

medium

A. XOR operator '^' is used incorrectly; should be '&&'

B. Loop runs one extra iteration causing out-of-bounds access

C. Variable 'result' is not initialized before XOR operation

D. Array size is incorrect causing runtime error

Solution

1. Step 1: Check variable initialization

   The variable 'result' is declared but not initialized, so XOR with garbage value leads to wrong result.

2. Step 2: Correct initialization

   Initialize 'result' to 0 before the loop to correctly accumulate XOR.

3. Final Answer:

   Variable 'result' is not initialized before XOR operation -> Option C

4. Quick Check:

   Initialize XOR accumulator to 0 [OK]

Hint: Always initialize XOR accumulator to 0 [OK]

Common Mistakes:

• Not initializing XOR variable
• Using wrong operator instead of ^
• Incorrect loop bounds

5. Given an array where every element appears twice except one element which appears once, how can you find the unique element efficiently using XOR? Choose the best approach.

hard

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

B. Sort the array and check neighbors for unique element

C. Use a hash map to count occurrences and find the unique element

D. Initialize a variable to 0 and XOR it with every element in the array once

Solution

1. Step 1: Use XOR properties for unique element

   XORing all elements cancels out duplicates because X XOR X = 0, leaving only the unique element.

2. Step 2: Implement efficient XOR approach

   Initialize a variable to 0 and XOR it with each element in one pass for O(n) time and O(1) space.

3. Final Answer:

   Initialize a variable to 0 and XOR it with every element in the array once -> Option D

4. Quick Check:

   Single pass XOR finds unique element efficiently [OK]

Hint: XOR all elements once; duplicates cancel out [OK]

Common Mistakes:

• Using sorting which is slower
• Using extra space with hash maps
• Incorrect arithmetic approach