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.