Two Non Repeating Elements in Array Using XOR in DSA C++ - Deep Dive

Overview - Two Non Repeating Elements in Array Using XOR

What is it?

This topic teaches how to find two unique numbers in an array where every other number repeats exactly twice. We use a special operation called XOR to do this efficiently without extra memory. XOR helps us identify differences between numbers by comparing their bits. This method is faster and uses less space than checking each number one by one.

Why it matters

Without this method, finding two unique numbers among duplicates would require extra memory or slower searching methods. This would make programs slower and use more resources, especially with large data. Using XOR makes the process quick and memory-friendly, which is important in real-world applications like error detection and data analysis.

Where it fits

Before learning this, you should understand basic arrays and the XOR operation. After this, you can explore more complex bit manipulation problems and advanced data structures that use similar tricks for optimization.

Mental Model

Core Idea

XOR helps isolate two unique numbers by canceling out duplicates and using bit differences to separate them.

Think of it like...

Imagine you have pairs of identical gloves mixed in a box, except two gloves are unique and unmatched. By comparing gloves pairwise and noticing differences, you can separate the two unique gloves without checking each glove individually.

Array: [a, a, b, b, x, y]
Step 1: XOR all elements -> xor = x ^ y
Step 2: Find rightmost set bit in xor -> mask
Step 3: Divide elements into two groups by mask bit
Group 1: elements with mask bit set
Group 2: elements without mask bit set
Step 4: XOR each group separately -> results are x and y

Diagram:
┌───────────────┐
│ Full XOR = x^y│
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Find mask bit │
└──────┬────────┘
       │
       ▼
┌───────────────┐       ┌───────────────┐
│ Group 1 XOR   │       │ Group 2 XOR   │
│ (mask bit=1)  │       │ (mask bit=0)  │
└──────┬────────┘       └──────┬────────┘
       │                       │
       ▼                       ▼
      x unique               y unique

Build-Up - 7 Steps

1

Foundation

Understanding XOR Basics

Concept: Learn what XOR does with bits and how it cancels duplicates.

XOR (^) compares two bits: if they are different, result is 1; if same, result is 0. Example: 0 ^ 0 = 0 1 ^ 1 = 0 0 ^ 1 = 1 1 ^ 0 = 1 Important property: x ^ x = 0 and x ^ 0 = x. This means XORing a number with itself cancels it out.

Result

XOR of two identical numbers is 0; XOR of a number with 0 is the number itself.

Understanding XOR's canceling property is key to removing duplicates without extra memory.

2

Foundation

XORing All Array Elements

Concept: XOR all elements to combine duplicates and isolate unique numbers.

Given array with pairs and two unique numbers, XOR all elements. Duplicates cancel out because x ^ x = 0. Result is XOR of two unique numbers: xor = x ^ y. Example: [2, 3, 2, 4, 3, 5] XOR all: 2^3^2^4^3^5 = (2^2)^(3^3)^(4^5) = 0^0^(4^5) = 4^5.

Result

xor holds combined difference of two unique numbers.

XORing the whole array reduces problem to finding two numbers from their combined XOR.

3

Intermediate

Finding a Differentiating Bit

🤔Before reading on: do you think any bit set in xor can help separate the two unique numbers? Commit to yes or no.

Concept: Identify a bit where the two unique numbers differ to split the array.

Since xor = x ^ y, at least one bit is 1 where x and y differ. Find rightmost set bit (mask) using: mask = xor & (-xor). This mask helps divide numbers into two groups based on that bit.

Result

mask isolates a bit that differs between the two unique numbers.

Knowing how to find a differing bit lets us separate numbers into groups containing one unique number each.

4

Intermediate

Dividing Array into Two Groups

🤔Before reading on: do you think grouping by mask bit will separate the unique numbers correctly? Commit to yes or no.

Concept: Split array elements into two groups based on the mask bit.

Group 1: elements with mask bit set (bit = 1). Group 2: elements with mask bit not set (bit = 0). Duplicates fall into same group and cancel out when XORed. Each group contains one unique number.

Result

Two groups formed, each with one unique number and duplicates.

Grouping by differing bit ensures unique numbers are isolated for separate XOR operations.

5

Intermediate

XORing Each Group to Find Unique Numbers

Concept: XOR elements in each group to find the unique numbers.

XOR all elements in Group 1 -> result is one unique number. XOR all elements in Group 2 -> result is the other unique number. Duplicates cancel out in each group. Example: Group 1: [4, 2, 2] XOR: 4 ^ 2 ^ 2 = 4 Group 2: [5, 3, 3] XOR: 5 ^ 3 ^ 3 = 5

Result

Two unique numbers found separately.

XORing groups leverages cancellation to reveal unique elements without extra memory.

6

Advanced

Complete C++ Implementation

🤔Before reading on: predict the output of the code when input is [1, 2, 1, 3, 2, 5]. Commit to your answer.

Concept: Putting all steps together in a runnable C++ program.

#include #include using namespace std; pair findTwoUnique(const vector& arr) { int xor_all = 0; for (int num : arr) { xor_all ^= num; } int mask = xor_all & (-xor_all); int x = 0, y = 0; for (int num : arr) { if (num & mask) x ^= num; else y ^= num; } return {x, y}; } int main() { vector arr = {1, 2, 1, 3, 2, 5}; auto result = findTwoUnique(arr); cout << result.first << " " << result.second << endl; return 0; }

Result

3 5

Seeing the full code confirms how XOR and bit masking combine to solve the problem efficiently.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think this method works if the array has more than two unique numbers? Commit to yes or no.

Concept: Understand limits and performance considerations of the XOR method.

This method only works if exactly two numbers are unique and others appear twice. If more unique numbers exist, XOR alone can't separate them. Time complexity is O(n), space is O(1), making it very efficient. For large data, this is faster and uses less memory than hash maps. Be careful with signed integers and negative numbers in mask calculation.

Result

Method fails with more than two unique numbers; otherwise, it's optimal.

Knowing method limits prevents misuse and guides choosing correct algorithms for different problems.

Under the Hood

XOR works at the bit level, comparing each bit of numbers. When XORing all elements, pairs cancel because identical bits produce 0. The remaining XOR is the bitwise difference of the two unique numbers. Finding the rightmost set bit isolates a bit where these two numbers differ. Splitting the array by this bit groups duplicates together and separates unique numbers. XORing each group cancels duplicates and reveals unique numbers.

Why designed this way?

This approach was designed to solve the problem in linear time and constant space, avoiding extra memory like hash tables. Bitwise operations are fast and supported directly by hardware. Alternatives like sorting or hash maps use more time or space. The method leverages XOR's unique properties to elegantly separate two unique elements.

Input Array
  │
  ▼
XOR all elements
  │
  ▼
xor = x ^ y (two unique numbers)
  │
  ▼
Find mask = rightmost set bit in xor
  │
  ▼
Split array into two groups by mask bit
  │           │
  ▼           ▼
Group 1      Group 2
  │           │
  ▼           ▼
XOR all in Group 1  XOR all in Group 2
  │           │
  ▼           ▼
Unique x     Unique y

Myth Busters - 3 Common Misconceptions

Quick: Does XORing the entire array always give one unique number? Commit yes or no.

Common Belief: XORing the whole array will give the single unique number if only one exists.

Reality: XORing the whole array gives the XOR of all unique numbers combined, not a single unique number if there are multiple unique elements.

Why it matters: Assuming XOR gives one unique number leads to wrong results when multiple unique numbers exist.

Quick: Can this method find unique numbers if duplicates appear more than twice? Commit yes or no.

Common Belief: This XOR method works even if duplicates appear more than twice.

Reality: The method only works correctly if duplicates appear exactly twice; more repetitions break the cancellation property.

Why it matters: Using this method with triplets or other counts causes incorrect unique number detection.

Quick: Is the mask always the leftmost set bit in xor? Commit yes or no.

Common Belief: The mask used to split groups is the leftmost set bit of xor.

Reality: The mask is the rightmost set bit of xor, found by xor & (-xor).

Why it matters: Choosing the wrong bit for mask can fail to separate unique numbers correctly.

Expert Zone

1

The choice of rightmost set bit as mask ensures at least one differing bit is used, simplifying group division.

2

Negative numbers in two's complement form work correctly with mask = xor & (-xor) due to bitwise arithmetic properties.

3

This method can be extended to find one unique number when others appear thrice using different bitwise tricks, but not directly for two unique numbers.

When NOT to use

Avoid this method if the array has more than two unique numbers or duplicates appear more than twice. Use hash maps or sorting for those cases.

Production Patterns

Used in embedded systems and performance-critical code where memory is limited. Also common in coding interviews to test bit manipulation skills.

Connections

Bit Manipulation

Builds-on

Mastering XOR for unique elements deepens understanding of bitwise operations used in many algorithms.

Hash Tables

Alternative approach

Knowing XOR method helps compare space-time tradeoffs with hash-based counting.

Error Detection in Communication

Similar pattern

XOR's canceling property is used in parity checks and error detection codes, linking algorithmic and hardware error correction.

Common Pitfalls

#1 Assuming XOR method works if duplicates appear more than twice.

Wrong approach:

vector arr = {1,1,1,2,2,2,3,4}; // Trying XOR method here
int xor_all = 0;
for (int num : arr) xor_all ^= num;
// Proceed as usual

Correct approach:

Use hash map counting for this input instead of XOR method.

Root cause:

Misunderstanding that XOR cancels only pairs, not triplets or other counts.

#2 Using leftmost set bit instead of rightmost set bit for mask.

Wrong approach:

int mask = 1 << (31 - __builtin_clz(xor_all)); // leftmost set bit

Correct approach:

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

Root cause:

Confusing bit operations and their effects on group separation.

#3 Not handling negative numbers correctly in mask calculation.

Wrong approach:

int mask = xor_all & (~xor_all + 1); // incorrect if xor_all negative

Correct approach:

int mask = xor_all & (-xor_all); // works with two's complement negative numbers

Root cause:

Lack of understanding of two's complement and bitwise negation.

Key Takeaways

XOR operation cancels pairs of identical numbers, leaving XOR of unique numbers.

Finding the rightmost set bit in XOR helps split numbers into two groups each containing one unique number.

XORing each group separately reveals the two unique numbers efficiently in linear time and constant space.

This method only works when exactly two unique numbers exist and all others appear twice.

Understanding bitwise operations and two's complement is essential for correct implementation.

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