Why Two Non Repeating Elements in Array Using XOR in DSA C#?

The Big Idea

What if you could find two unique items in a huge pile instantly, without checking each pair?

The Scenario

Imagine you have a big box of socks where every sock has a matching pair except for two unique socks. You want to find those two unique socks quickly without checking every single sock against all others.

The Problem

Manually comparing each sock with every other sock takes a lot of time and effort. It's easy to miss pairs or get confused, especially if the box is huge. This slow and error-prone method wastes your time and energy.

The Solution

Using XOR, a special operation, you can cleverly find the two unique socks in just one pass. XOR cancels out pairs automatically, leaving only the unique socks. This method is fast, simple, and reliable.

Before vs After

✗ Before

for (int i = 0; i < arr.Length; i++) {
  for (int j = i + 1; j < arr.Length; j++) {
    if (arr[i] == arr[j]) {
      // mark as paired
    }
  }
}
// find unmarked elements

✓ After

int xorResult = 0;
foreach (int num in arr) {
  xorResult ^= num;
}
// use xorResult to find two unique numbers

What It Enables

This technique lets you find two unique elements in a large collection instantly, without extra memory or complex checks.

Real Life Example

Finding two unique defective products in a batch where all others are identical pairs, quickly and without sorting or extra storage.

Key Takeaways

Manual pair checking is slow and error-prone.

XOR operation cancels pairs and reveals unique elements efficiently.

This method works in linear time with constant extra space.

Practice

1. What is the main purpose of using XOR operation to find two non-repeating elements in an array where all other elements repeat 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 behavior with 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, isolating their combined difference.

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
• Confusing XOR with counting 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 in an integer array arr?

easy

A. int xor = 0;

B. int xor = arr[0];

C. int xor = -1;

D. int xor = 1;

Solution

1. Step 1: Understand XOR identity element

   XOR with 0 leaves the number unchanged, so start with 0 to accumulate XOR of all elements.

2. Step 2: Initialization correctness

   Initializing xor to 0 ensures correct cumulative XOR of array elements.

3. Final Answer:

   int xor = 0; -> Option A

4. Quick Check:

   Start XOR with 0 to accumulate values correctly [OK]

Hint: Start XOR with 0 because 0 ^ x = x [OK]

Common Mistakes:

• Starting XOR with 1 changes results
• Using negative numbers without reason
• Initializing with first array element causes errors

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

int[] arr = {2, 3, 7, 9, 2, 3};
int xor = 0;
foreach (int num in arr) {
    xor ^= num;
}
Console.WriteLine(xor);

medium

A. 9

B. 0

C. 7

D. 14

Solution

1. Step 1: XOR all elements in the array

   Calculate xor = 2 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3. Since 2 ^ 2 = 0 and 3 ^ 3 = 0, this reduces to 7 ^ 9.

2. Step 2: Calculate XOR of remaining unique elements

   7 in binary: 0111, 9 in binary: 1001 XOR: 0111 ^ 1001 = 1110 (binary) = 14 (decimal).

3. Final Answer:

   14 -> Option D

4. Quick Check:

   Duplicates cancel, XOR unique = 7 ^ 9 = 14 [OK]

Hint: Duplicates XOR to zero, XOR unique elements left [OK]

Common Mistakes:

• Forgetting duplicates cancel out
• Calculating XOR incorrectly
• Assuming output is one unique element

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

int[] arr = {4, 1, 2, 1, 2, 5};
int xor = 0;
foreach (int num in arr) {
    xor ^= num;
}
int setBit = xor & ~(xor - 1);
int x = 0, y = 0;
foreach (int num in arr) {
    if ((num & setBit) == 0)
        x ^= num;
    else
        y ^= num;
}
Console.WriteLine(x + ", " + y);

medium

A. The expression to find setBit is incorrect; it should be 'xor & (-xor)' instead of 'xor & ~(xor - 1)'

B. The initial xor should start with arr[0] instead of 0

C. No error; the code will output the two unique elements correctly

D. The if condition should check '(num & setBit) != 0' instead of '== 0'

Solution

1. Step 1: Check how setBit is calculated

   In two's complement, 'xor & ~(xor - 1)' is equivalent to 'xor & (-xor)', both isolate the rightmost set bit correctly.

2. Step 2: Verify code execution

   arr={4,1,2,1,2,5}, xor=4^5=1, setBit=1. Partitions: x=4 (evens), y=5 (odds). Outputs '4, 5' correctly.

3. Final Answer:

   No error; the code will output the two unique elements correctly -> Option C

4. Quick Check:

   Expressions equivalent, code partitions and XORs correctly [OK]

Hint: xor & ~(xor-1) == xor & -xor for rightmost set bit [OK]

Common Mistakes:

• Thinking 'xor & ~(xor-1)' differs from 'xor & -xor'
• Starting xor with first element instead of 0
• Confusing if condition for partitioning

5. Given an array arr = {10, 20, 10, 30, 40, 20}, write the final two non-repeating elements found using the XOR method. What are these elements?

hard

A. [10, 20]

B. [30, 40]

C. [10, 30]

D. [20, 40]

Solution

1. Step 1: XOR all elements to get combined XOR

   Calculate xor = 10 ^ 20 ^ 10 ^ 30 ^ 40 ^ 20. Duplicates cancel: 10 ^ 10 = 0, 20 ^ 20 = 0. Remaining xor = 30 ^ 40.

2. Step 2: Calculate XOR of 30 and 40

   30 in binary: 00011110, 40 in binary: 00101000 XOR: 00011110 ^ 00101000 = 00110110 (54 decimal). Use this to separate elements and find unique ones: 30 and 40.

3. Final Answer:

   [30, 40] -> Option B

4. Quick Check:

   Duplicates cancel, unique elements are 30 and 40 [OK]

Hint: Duplicates cancel, XOR leaves unique pair [OK]

Common Mistakes:

• Including duplicates as unique
• Mixing up XOR results
• Not cancelling duplicates properly