Two Non Repeating Elements in Array Using XOR in DSA Python - 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 set bit

↓

XOR elements in each group separately

↓

Get two unique numbers

↓

Done

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

Execution Sample

DSA Python

arr = [2, 1, 7, 9, 2, 1]
xor_all = 0
for num in arr:
    xor_all ^= num
set_bit = xor_all & (-xor_all)
num1 = 0
num2 = 0
for num in arr:
    if num & set_bit:
        num1 ^= num
    else:
        num2 ^= num
print(num1, num2)

This code finds two unique numbers in an array where all others repeat twice using XOR.

Execution Table

Step	Operation	xor_all	set_bit	num1	num2	Visual State
1	XOR with 2	0 ^ 2 = 2				[2]
2	XOR with 1	2 ^ 1 = 3				[2,1]
3	XOR with 7	3 ^ 7 = 4				[2,1,7]
4	XOR with 9	4 ^ 9 = 13				[2,1,7,9]
5	XOR with 2	13 ^ 2 = 15				[2,1,7,9,2]
6	XOR with 1	15 ^ 1 = 14				[2,1,7,9,2,1]
7	Find rightmost set bit of xor_all=14	14	2 (binary 10)
8	Divide and XOR group with set bit	14	2	0 ^ 2 = 2	0	[Group1: 2,2,7; Group2: 1,1,9]
9	XOR with 2 in group1	14	2	2 ^ 2 = 0	0	[Group1: 2,2,7]
10	XOR with 7 in group1	14	2	0 ^ 7 = 7	0	[Group1: 2,2,7]
11	Divide and XOR group without set bit	14	2	7	0 ^ 1 = 1	[Group2: 1,1,9]
12	XOR with 1 in group2	14	2	7	1 ^ 1 = 0	[Group2: 1,1,9]
13	XOR with 9 in group2	14	2	7	0 ^ 9 = 9	[Group2: 1,1,9]
14	Result unique numbers	14	2	7	9	Unique numbers found: 7 and 9
15	End	14	2	7	9	Done

💡 All elements processed; two unique numbers 7 and 9 found.

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 14	Final
xor_all	0	14	14	14	14
set_bit			2	2	2
num1	0	0	0	7	7
num2	0	0	0	9	9

Key Moments - 3 Insights

Why do we XOR all elements first?

XORing all elements cancels out duplicates because x ^ x = 0, leaving XOR of 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-13).

Visual Quiz - 3 Questions

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

A 15

B 14

C 13

D 6

💡 Hint

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

At which step does num1 become 7?

A Step 9

B Step 14

C Step 10

D Step 13

💡 Hint

Look at 'num1' column in execution_table; it changes to 7 at step 10.

If the set_bit was 4 instead of 2, how would the groups change?

A Different elements would be grouped, changing num1 and num2 values

B Groups remain the same, no effect

C All elements go to one group

D No unique numbers found

💡 Hint

The set_bit determines grouping; changing it changes which elements XOR together (see concept_flow).

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 array into two groups by this bit.
4. XOR each group to find unique numbers.
5. Works because duplicates cancel out in XOR.
6. Efficient O(n) time, O(1) space method.

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 the XOR of the two unique numbers. Then find the rightmost set bit in xor_all to split the array into two groups. Each group contains one unique number and duplicates. XORing each group separately cancels duplicates, leaving the unique numbers. The execution table shows step-by-step XOR operations and groupings. Variable tracker follows xor_all, set_bit, num1, and num2 values. 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 no extra space.

Practice

1. What is the main purpose of using XOR operation to find two non-repeating elements in an array where every other element repeats twice?

easy

A. To sort the array in ascending order

B. To count the frequency of each element

C. To cancel out all repeating elements and isolate the XOR of the two unique elements

D. To reverse the array elements

Solution

1. Step 1: Understand XOR properties

   XOR of a number with itself is 0, and XOR with 0 is the number itself. This helps cancel out repeating elements.

2. Step 2: Apply XOR on all elements

   When XOR is applied on the entire array, all repeating elements cancel out, leaving XOR of the two unique elements.

3. Final Answer:

   To cancel out all repeating elements and isolate the XOR of the two unique elements -> Option C

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
• Using XOR to count frequencies
• Assuming XOR reverses elements

2. Which of the following Python code snippets correctly initializes the XOR of all elements in a list named arr to zero before processing?

easy

A. xor = 1

B. xor = 0

C. xor = arr[0]

D. xor = None

Solution

1. Step 1: Initialize XOR variable

   We start XOR with 0 because XOR with 0 returns the other number unchanged.

2. Step 2: Confirm initialization correctness

   Starting with 0 ensures the first XOR operation correctly sets the value to the first element.

3. Final Answer:

   xor = 0 -> Option B

4. Quick Check:

   Initialize XOR with 0 for correct accumulation [OK]

Hint: Start XOR with 0 to accumulate correctly [OK]

Common Mistakes:

• Initializing XOR with 1 causes wrong results
• Using first element without XOR 0 initialization
• Setting XOR to None causes errors

3. What will be the output of the following Python code?

arr = [2, 3, 7, 9, 2, 3]
xor = 0
for num in arr:
    xor ^= num
print(xor)

medium

A. 0

B. 9

C. 7

D. 14

Solution

1. Step 1: XOR all elements in the array

   Calculate XOR stepwise: 0^2=2, 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Final XOR value

   The final XOR after processing all elements is 14.

3. Final Answer:

   14 -> Option D

4. Quick Check:

   Stepwise XOR = 14 [OK]

Hint: XOR all elements stepwise to find combined XOR [OK]

Common Mistakes:

• Forgetting XOR is cumulative and order matters
• Mistaking XOR with addition
• Stopping XOR early

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

arr = [4, 1, 2, 1, 2, 5]
xor = 0
for num in arr:
    xor ^= num
set_bit = xor & ~(xor - 1)
num1 = 0
num2 = 0
for num in arr:
    if (num & set_bit) > 0:
        num1 ^= num
    else:
        num2 ^= num
print(num1, num2)

medium

A. No error, code works correctly

B. XOR initialization should be arr[0] instead of 0

C. Incorrect calculation of set_bit using bitwise NOT

D. Using > 0 instead of != 0 in if condition

Solution

1. Step 1: Check set_bit calculation

   set_bit = xor & ~(xor - 1) correctly isolates rightmost set bit.

2. Step 2: Verify partition and XOR groups

   Elements are split by set_bit and XORed separately to find unique elements.

3. Step 3: Confirm output correctness

   Code correctly prints the two unique numbers without errors.

4. Final Answer:

   No error, code works correctly -> Option A

5. Quick Check:

   Correct set_bit and partitioning = code works [OK]

Hint: Use xor & ~(xor-1) to find rightmost set bit correctly [OK]

Common Mistakes:

• Misusing bitwise NOT causing wrong set_bit
• Initializing XOR incorrectly
• Using wrong condition in if statement

5. Given an array arr = [10, 20, 10, 30, 40, 20], which of the following Python code snippets correctly finds the two non-repeating elements using XOR and prints them in ascending order?

hard

A. xor = 0
for num in arr:
xor ^= num
set_bit = xor & (-xor)
num1 = 0
num2 = 0
for num in arr:
if num & set_bit:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

B. xor = 0
for num in arr:
xor ^= num
set_bit = xor | (xor - 1)
num1 = 0
num2 = 0
for num in arr:
if num & set_bit:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

C. xor = arr[0]
for num in arr[1:]:
xor ^= num
set_bit = xor & ~(xor - 1)
num1 = 0
num2 = 0
for num in arr:
if (num & set_bit) == 0:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

D. xor = 0
for num in arr:
xor ^= num
set_bit = xor & ~(xor + 1)
num1 = 0
num2 = 0
for num in arr:
if (num & set_bit) != 0:
num1 ^= num
else:
num2 ^= num
print(sorted([num1, num2]))

Solution

1. Step 1: Calculate XOR of all elements

   xor accumulates XOR of all elements, isolating XOR of two unique numbers.

2. Step 2: Find rightmost set bit correctly

   set_bit = xor & (-xor) correctly isolates the rightmost set bit for partitioning.

3. Step 3: Partition elements and XOR separately

   Elements are split by set_bit and XORed to find the two unique numbers.

4. Step 4: Sort and print unique elements

   Sorting ensures output is in ascending order as required.

5. Final Answer:

   Code in option A correctly finds and prints [30, 40] -> Option A

6. Quick Check:

   Rightmost set bit with xor & (-xor) + partition = correct [OK]

Hint: Use xor & (-xor) to find set bit and partition array [OK]

Common Mistakes:

• Using incorrect set_bit calculation like xor | (xor - 1)
• Wrong initialization of xor variable
• Incorrect condition in partition if statement