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.

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 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 property for 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 because duplicates cancel out.

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
• Using XOR to count 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?

easy

A. int xor = 1;

B. int xor = 0;

C. int xor = -1;

D. int xor = NULL;

Solution

1. Step 1: Understand XOR identity element

   XOR with 0 leaves the number unchanged, so start with 0.

2. Step 2: Initialize XOR variable

   Setting xor = 0 allows XORing all elements correctly.

3. Final Answer:

   int xor = 0; -> Option B

4. Quick Check:

   Start XOR with 0 for correct accumulation [OK]

Hint: Initialize XOR with 0 because 0 XOR x = x [OK]

Common Mistakes:

• Initializing XOR with 1 or -1
• Using NULL for integer variable
• Not initializing XOR variable

3. What will be the output of the following C code snippet?

int arr[] = {2, 3, 7, 9, 2, 3};
int xor = 0;
for(int i = 0; i < 6; i++) {
    xor ^= arr[i];
}
printf("%d", xor);

medium

A. 14

B. 9

C. 7

D. 0

Solution

1. Step 1: XOR all elements in the array

   Calculate 2^3=1, 1^7=6, 6^9=15, 15^2=13, 13^3=14.

2. Step 2: Result after XORing all elements

   The final XOR value is 14, which is XOR of the two unique elements 7 and 9.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   XOR all elements = 14 [OK]

Hint: XOR all elements to get XOR of unique pair [OK]

Common Mistakes:

• Stopping XOR early
• Miscomputing XOR values
• Assuming output is one unique element

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

int arr[] = {4, 1, 2, 1, 2, 5};
int xor = 0;
for(int i = 0; i < 6; i++) {
    xor ^= arr[i];
}
int set_bit = xor & ~(xor - 1);
int x = 0, y = 0;
for(int i = 0; i < 6; i++) {
    if(arr[i] & set_bit)
        x ^= arr[i];
    else
        y ^= arr[i];
}
printf("%d %d", x, y);

medium

A. Incorrect calculation of set_bit using xor & ~(xor - 1)

B. Loop range should be 0 to 5, not 0 to 6

C. Missing initialization of x and y to zero

D. No error, code works correctly

Solution

1. Step 1: Check set_bit calculation

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

2. Step 2: Verify loops and initialization

   Loops run from 0 to 5 (6 elements), x and y initialized to 0 correctly.

3. Final Answer:

   No error, code works correctly -> Option D

4. Quick Check:

   Code logic and syntax are correct [OK]

Hint: Check bitwise operations and loop ranges carefully [OK]

Common Mistakes:

• Miscomputing set_bit
• Wrong loop boundaries
• Uninitialized variables

5. Given an array where exactly two elements appear once and all others appear twice, how can you find those two unique elements efficiently using XOR? Choose the correct sequence of steps.

hard

A. Sort the array, then scan to find unique elements

B. Use a hash map to count frequencies, then pick elements with count 1

C. XOR all elements, find rightmost set bit in XOR result, divide elements into two groups by that bit, XOR each group separately

D. XOR all elements twice to get unique elements

Solution

1. Step 1: XOR all elements to get XOR of two unique elements

   This cancels out duplicates and leaves XOR of unique pair.

2. Step 2: Find rightmost set bit in XOR result

   This bit differs between the two unique elements.

3. Step 3: Divide elements into two groups based on this bit and XOR each group

   This separates the two unique elements and finds them individually.

4. Final Answer:

   XOR all elements, find rightmost set bit in XOR result, divide elements into two groups by that bit, XOR each group separately -> Option C

5. Quick Check:

   Use XOR and bit partitioning to find unique elements [OK]

Hint: Use XOR and bit mask to split and find unique elements [OK]

Common Mistakes:

• Sorting instead of XOR
• Using hash map (extra space)
• XORing twice without grouping