Two Non Repeating Elements in Array Using XOR in DSA C# - Execution Trace

Concept Flow - Two Non Repeating Elements in Array Using XOR

Start with array

↓

XOR all elements

→Get XOR of two unique numbers

↓

Find rightmost set bit in XOR result

↓

Divide elements into two groups based on set bit

↓

XOR elements in each group separately

↓

Result: two unique numbers found

We XOR all elements to get combined XOR of two unique numbers, find a set bit to split elements into two groups, then XOR each group to find the unique numbers.

Execution Sample

DSA C#

int[] arr = {2, 3, 7, 9, 2, 3};
int xor = 0;
foreach (int num in arr) xor ^= num;
int setBit = xor & (-xor);
int x = 0, y = 0;
foreach (int num in arr) {
  if ((num & setBit) != 0) x ^= num; else y ^= num;
}

This code finds two unique numbers in an array where all others repeat by using XOR and bit manipulation.

Execution Table

Step	Operation	XOR Value	Set Bit	Group X XOR	Group Y XOR	Unique Elements Found
1	XOR all elements: 0 ^ 2	2	-	-	-	-
2	XOR all elements: 2 ^ 3	1	-	-	-	-
3	XOR all elements: 1 ^ 7	6	-	-	-	-
4	XOR all elements: 6 ^ 9	15	-	-	-	-
5	XOR all elements: 15 ^ 2	13	-	-	-	-
6	XOR all elements: 13 ^ 3	14	-	-	-	-
7	Find rightmost set bit of 14	14	2 (binary 10)	-	-	-
8	Divide elements into groups and XOR group X	-	2	2	-	-
9	Group X XOR: 2 ^ 3	-	2	1	-	-
10	Group X XOR: 1 ^ 7	-	2	6	-	-
11	Group Y XOR: 0 ^ 9	-	2	6	9	-
12	Group X XOR: 6 ^ 2	-	2	4	9	-
13	Group X XOR: 4 ^ 3	-	2	7	9	-
14	Unique elements found	-	2	7	9	7 and 9

💡 All elements processed, two unique numbers 7 and 9 found by XOR groups.

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 11	After Step 13	Final
xor	0	14	14	14	14	14
setBit	-	-	2	2	2	2
x (Group X XOR)	0	0	0	6	7	7
y (Group Y XOR)	0	0	0	9	9	9

Key Moments - 3 Insights

Why do we XOR all elements first before splitting into groups?

XORing all elements gives combined XOR of the two unique numbers, which helps find a bit where they differ (see steps 1-6 in execution_table).

How does finding the rightmost set bit help in separating the two unique numbers?

The rightmost set bit in XOR result shows a bit where the two unique numbers differ, so splitting elements by this bit separates them into two groups (step 7).

Why do we XOR elements in each group separately after splitting?

Because duplicates appear in both groups and cancel out, XORing each group leaves only the unique number in that group (steps 8-13).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the value of setBit?

A 2

B 1

C 4

D 8

💡 Hint

Check the 'Set Bit' column at step 7 in execution_table.

At which step does the Group Y XOR become 9?

A Step 10

B Step 11

C Step 9

D Step 13

💡 Hint

Look at the 'Group Y XOR' column in execution_table for the value 9.

If the array had an extra unique number, how would the final XOR value change after step 6?

A It would be zero

B It would be the same

C It would be XOR of three unique numbers

D It would be negative

💡 Hint

Refer to the 'XOR Value' column after step 6 in execution_table and think about XOR properties.

Concept Snapshot

Two Non Repeating Elements Using XOR:
1. XOR all elements to get xor of two unique numbers.
2. Find rightmost set bit in XOR result.
3. Split array into two groups by this bit.
4. XOR each group to find unique numbers.
5. Duplicates cancel out in XOR.

Full Transcript

This concept finds two unique numbers in an array where all other numbers repeat twice. First, XOR all elements to get combined XOR of the two unique numbers. Then find the rightmost set bit in this XOR result to identify a bit where the two unique numbers differ. Next, split the array into two groups based on whether elements have this bit set or not. XOR elements in each group separately to isolate each unique number, since duplicates cancel out. The final result is the two unique numbers. The execution table shows step-by-step XOR calculations and groupings, and the variable tracker shows how key variables change. Key moments clarify why XOR is used first, how the set bit helps split groups, and why XORing groups isolates unique numbers.

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