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

Concept Flow - Two Non Repeating Elements in Array Using XOR

XOR all elements

→Result = XOR of two unique numbers

↓

Find rightmost set bit in Result

↓

Divide elements into two groups based on this bit

↓

XOR elements in each group separately

↓

Get two unique numbers

↓

Done

We first XOR all numbers to get XOR of two unique numbers. Then find a set bit to split numbers into two groups. XOR each group to find the unique numbers.

Execution Sample

DSA C++

int arr[] = {2, 3, 7, 9, 2, 3};
int xor_all = 0;
for (int num : arr) xor_all ^= num;
int set_bit = xor_all & (-xor_all);
int x = 0, y = 0;
for (int num : arr) {
  if (num & set_bit) x ^= num; else y ^= num;
}

This code finds two unique numbers in the array where all others repeat twice.

Execution Table

Step	Operation	xor_all	set_bit	Group X XOR	Group Y XOR	Visual State
1	XOR 2	0 ^ 2 = 2				[2]
2	XOR 3	2 ^ 3 = 1				[2,3]
3	XOR 7	1 ^ 7 = 6				[2,3,7]
4	XOR 9	6 ^ 9 = 15				[2,3,7,9]
5	XOR 2	15 ^ 2 = 13				[2,3,7,9,2]
6	XOR 3	13 ^ 3 = 14				[2,3,7,9,2,3]
7	Find rightmost set bit of 14	14	2 (binary 10)
8	Divide and XOR group X (bit set)		2	2 ^ 7 = 5		Group X: [2, 7]
9	Divide and XOR group Y (bit not set)		2		3 ^ 9 ^ 3 = 9	Group Y: [3, 9, 3]
10	Final unique numbers			5	9	Unique elements: 5 and 9
11	Group XOR results			5	9	x=5, y=9
12	Done			5	9	Result: 5 and 9

💡 All elements processed, two unique numbers found by XOR in separate groups.

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 9	Final
xor_all	0	14	14	14	14
set_bit	N/A	N/A	2	2	2
x (Group X XOR)	0	0	0	5	5
y (Group Y XOR)	0	0	0	9	9

Key Moments - 3 Insights

Why do we XOR all elements first?

XORing all elements cancels out duplicates and leaves XOR of the two unique numbers (see execution_table steps 1-6).

How do we find the rightmost set bit in xor_all?

Using 'xor_all & (-xor_all)' isolates the rightmost set bit (step 7), which helps split numbers into two groups.

Why split elements into two groups based on the set bit?

Because the two unique numbers differ at that bit, splitting ensures each unique number falls into a different group (steps 8-9).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of xor_all?

A 14

B 15

C 13

D 6

💡 Hint

Check the 'xor_all' column at step 6 in execution_table.

At which step is the rightmost set bit found?

A Step 5

B Step 7

C Step 9

D Step 11

💡 Hint

Look for the step where 'set_bit' is assigned in execution_table.

If the array had no duplicates, how would the xor_all value change after step 6?

A It would be zero

B It would be the sum of all elements

C It would be XOR of all unique elements

D It would be the first element

💡 Hint

Recall XOR operation properties shown in variable_tracker for xor_all.

Concept Snapshot

Two Non Repeating Elements Using XOR:
1. XOR all elements to get xor_all = unique1 ^ unique2.
2. Find rightmost set bit in xor_all.
3. Split elements into two groups by this bit.
4. XOR each group to find unique elements.
5. Works because duplicates cancel out in XOR.

Full Transcript

This concept finds two unique numbers in an array where all others repeat twice. First, XOR all elements to get xor_all, which equals XOR of the two unique numbers. Then find the rightmost set bit in xor_all to split elements into two groups. Each unique number falls into a different group because they differ at that bit. XORing each group separately cancels duplicates and reveals the unique numbers. The execution table shows step-by-step XOR operations, bit finding, grouping, and final results. Variable tracker shows how xor_all, set_bit, and group XORs change. Key moments clarify why XOR is used, how the set bit is found, and why splitting works. The visual quiz tests understanding of these steps. This method is efficient and uses bitwise operations to solve the problem without extra space.

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