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

↓

Compute XOR of all elements

↓

Find rightmost set bit in XOR result

↓

Divide elements into two groups based on set bit

↓

Compute XOR of each group separately

↓

Result: two unique non-repeating elements

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

Execution Sample

DSA C

int arr[] = {2, 3, 7, 9, 2, 3};
int n = 6;
int xor_all = 0;
for (int i = 0; i < n; i++) {
  xor_all ^= arr[i];
}

This code computes XOR of all elements in the array.

Execution Table

Step	Operation	XOR All So Far	Rightmost Set Bit	Group 1 XOR	Group 2 XOR	Visual State
1	XOR arr[0]=2	0 ^ 2 = 2				[2]
2	XOR arr[1]=3	2 ^ 3 = 1				[2,3]
3	XOR arr[2]=7	1 ^ 7 = 6				[2,3,7]
4	XOR arr[3]=9	6 ^ 9 = 15				[2,3,7,9]
5	XOR arr[4]=2	15 ^ 2 = 13				[2,3,7,9,2]
6	XOR arr[5]=3	13 ^ 3 = 14	14 & (-14) = 2			[2,3,7,9,2,3]
7	Divide elements by set bit 2	14	2	XOR of elements with bit 2 set	XOR of elements without bit 2 set
8	Group 1 XOR: 2,3,7,2,3		2	0 ^ 2 ^ 3 ^ 7 ^ 2 ^ 3 = 7		[Group1: 2,3,7,2,3]
9	Group 2 XOR: 9		2		0 ^ 9 = 9	[Group2: 9]
10	Final unique elements		2	7	9	Unique elements: 7 and 9

💡 All elements processed, groups XORed, unique elements found as 7 and 9

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
xor_all	0	2	1	6	15	13	14	14	14	14	14
rightmost_set_bit							2	2	2	2	2
group1_xor	0	0	0	0	0	0	0	0	7	7	7
group2_xor	0	0	0	0	0	0	0	0	0	9	9

Key Moments - 3 Insights

Why do we XOR all elements first instead of directly finding unique elements?

XORing all elements gives XOR of the two unique numbers combined, which helps us find a bit where they differ (see step 6 in execution_table). This bit is used to separate elements into two groups.

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

The rightmost set bit in xor_all shows a bit where the two unique numbers differ. Dividing elements by this bit ensures each unique number falls into different groups (step 7).

Why do duplicates XOR to zero in their groups?

Because XOR of a number with itself is zero, duplicates cancel out in their groups, leaving only the unique element (steps 8 and 9).

Visual Quiz - 3 Questions

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

A 14

B 13

C 15

D 6

💡 Hint

Check the 'XOR All So Far' column at step 6 in execution_table.

At which step do we find the rightmost set bit of xor_all?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for the step where 'Rightmost Set Bit' column is first filled in execution_table.

If the array had no duplicates, how would the 'Group 1 XOR' and 'Group 2 XOR' change?

A They would both be zero

B They would be equal

C They would be the two unique elements themselves

D They would be the same as xor_all

💡 Hint

Refer to the logic in steps 8 and 9 where groups XOR to unique elements.

Concept Snapshot

Two Non Repeating Elements Using XOR:
1. XOR all elements to get xor_all.
2. Find rightmost set bit in xor_all.
3. Divide elements into two groups by this bit.
4. XOR each group to get unique elements.
Duplicates cancel out by XOR property.

Full Transcript

This concept finds two unique non-repeating elements in an array where all other elements repeat twice. We XOR all elements to get xor_all, which is XOR of the two unique numbers. Then we find the rightmost set bit in xor_all to separate elements into two groups. Each group contains one unique number and duplicates. XORing each group cancels duplicates and reveals the unique numbers. The execution table shows step-by-step XOR calculations and group divisions. Variable tracker follows xor_all, rightmost set bit, and group XORs. Key moments clarify why XOR is used and how groups separate unique elements. Visual quiz tests understanding of xor_all value, step of finding set bit, and group XOR results.