Two Non Repeating Elements in Array Using XOR in DSA Javascript - 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 separately in each group

↓

Result: two unique non-repeating elements

We first XOR all elements to get XOR of two unique numbers. Then find a bit where they differ to split array into two groups. XOR each group to find the unique elements.

Execution Sample

DSA Javascript

const arr = [2, 3, 7, 9, 2, 3];
let xor = 0;
for (const num of arr) xor ^= num;
const setBit = xor & -xor;
let x = 0, y = 0;
for (const num of arr) {
  if (num & setBit) x ^= num; else y ^= num;
}
console.log(x, y);

This code finds two unique numbers in an array where all other numbers repeat twice.

Execution Table

Step	Operation	XOR Value	Set Bit	Group X XOR	Group Y XOR	Visual State
1	XOR all elements: 0 ^ 2	2	-	-	-	[2]
2	XOR all elements: 2 ^ 3	1	-	-	-	[2,3]
3	XOR all elements: 1 ^ 7	6	-	-	-	[2,3,7]
4	XOR all elements: 6 ^ 9	15	-	-	-	[2,3,7,9]
5	XOR all elements: 15 ^ 2	13	-	-	-	[2,3,7,9,2]
6	XOR all elements: 13 ^ 3	14	-	-	-	[2,3,7,9,2,3]
7	Find rightmost set bit in 14	14	2 (binary 10)	-	-	XOR=14, setBit=2
8	Second loop: num=2 & 2 !=0, x=0 ^ 2	-	2	2	-	Group X: [2]
9	num=3 & 2 !=0, x=2 ^ 3 =1	-	2	1	-	Group X: [2,3]
10	num=7 & 2 !=0, x=1 ^ 7 =6	-	2	6	-	Group X: [2,3,7]
11	num=9 & 2 ==0, y=0 ^ 9 =9	-	2	6	9	Group Y: [9]
12	num=2 & 2 !=0, x=6 ^ 2 =4	-	2	4	9	Group X: [2,3,7,2]
13	num=3 & 2 !=0, x=4 ^ 3 =7	-	2	7	9	Group X: [2,3,7,2,3], Group Y: [9]
14	Result: two unique elements	-	-	7	9	Unique elements: 7 and 9
15	End	-	-	7	9	All elements processed

💡 All elements processed and two unique non-repeating elements found.

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 14
xor	0	14	14	14
setBit	-	-	2	2
x (Group X XOR)	0	0	0	7
y (Group Y XOR)	0	0	0	9

Key Moments - 3 Insights

Why do we XOR all elements first?

XORing all elements cancels out numbers appearing twice, leaving XOR of two unique numbers (see execution_table steps 1-6).

How do we find the rightmost set bit in XOR?

We use 'xor & -xor' to isolate the rightmost set bit (step 7), which helps split elements into two groups.

Why split elements into two groups based on set bit?

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

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the value of setBit?

A 1

B 2

C 4

D 8

💡 Hint

Check the 'Set Bit' column at step 7 in execution_table.

At which step does the XOR of group X become 7?

A Step 13

B Step 11

C Step 9

D Step 14

💡 Hint

Look at 'Group X XOR' column in execution_table rows 8-14.

If the array had no repeating elements, how would the initial XOR value change?

A It would be zero

B It would be the sum of all elements

C It would be the XOR of all unique elements

D It would be the product of all elements

💡 Hint

Refer to the 'XOR Value' column in execution_table steps 1-6.

Concept Snapshot

Two Non Repeating Elements Using XOR:
1. XOR all elements to get xor of two unique numbers.
2. Find rightmost set bit in XOR result (xor & -xor).
3. Split array into two groups by this bit.
4. XOR each group separately to find unique elements.
5. Works because duplicates cancel out in XOR.
6. Time: O(n), Space: O(1).

Full Transcript

This concept finds two unique non-repeating elements in an array where all other elements repeat twice. First, XOR all elements to get XOR of the two unique numbers. Then find the rightmost set bit in this XOR to split the array into two groups. Each group contains one unique number and duplicates. XORing each group separately cancels duplicates and reveals the unique numbers. The execution table shows step-by-step XOR calculations and group divisions. The variable tracker follows key variables like xor, setBit, and group XORs. 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 constant extra space.

Practice

1. What is the main purpose of using XOR operation to find two non-repeating elements in an array?

easy

A. To cancel out all repeating elements and isolate the unique ones

B. To sort the array in ascending order

C. To count the total number of elements in the array

D. To reverse the array elements

Solution

1. Step 1: Understand XOR behavior with duplicates

   XOR of two identical numbers is 0, so repeating elements cancel out.

2. Step 2: Isolate unique elements using XOR

   XOR of all elements leaves XOR of two unique elements, isolating them.

3. Final Answer:

   To cancel out all repeating elements and isolate the unique ones -> Option A

4. Quick Check:

   XOR cancels duplicates = isolate unique elements [OK]

Hint: XOR cancels pairs, leaving only unique elements [OK]

Common Mistakes:

• Thinking XOR sorts the array
• Using XOR to count elements
• Assuming XOR reverses arrays

2. Which of the following JavaScript code snippets correctly initializes the XOR variable to find two non-repeating elements?

easy

A. let xor = null;

B. let xor = 1;

C. let xor = 0;

D. let xor = undefined;

Solution

1. Step 1: Understand XOR identity element

   XOR with 0 returns the other number unchanged, so start with 0.

2. Step 2: Initialize XOR variable correctly

   Initialize xor as 0 to accumulate XOR of all elements properly.

3. Final Answer:

   let xor = 0; -> Option C

4. Quick Check:

   Start XOR with 0 for correct accumulation [OK]

Hint: Initialize XOR with 0, not 1 or null [OK]

Common Mistakes:

• Starting XOR with 1 changes results
• Using null or undefined causes errors
• Not initializing XOR variable

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

const arr = [2, 3, 7, 9, 2, 3];
let xor = 0;
for (const num of arr) {
  xor ^= num;
}
console.log(xor);

medium

A. 7

B. 0

C. 9

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 value after processing all elements is 14.

3. Final Answer:

   14 -> Option D

4. Quick Check:

   XOR all elements = 14 [OK]

Hint: XOR duplicates cancel; XOR unique pairs remain [OK]

Common Mistakes:

• Miscomputing XOR 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:

const arr = [4, 1, 2, 1, 2, 5];
let xor = 0;
for (let i = 0; i <= arr.length; i++) {
  xor ^= arr[i];
}
console.log(xor);

medium

A. Use let xor = null instead of 0

B. Loop condition should be i < arr.length, not i <= arr.length

C. Array elements should be sorted before XOR

D. XOR should start from 1, not 0

Solution

1. Step 1: Check loop boundary condition

   The loop runs from i=0 to i<=arr.length, which accesses arr[arr.length] (undefined).

2. Step 2: Correct loop condition

   Change condition to i < arr.length to avoid accessing undefined and runtime error.

3. Final Answer:

   Loop condition should be i < arr.length, not i <= arr.length -> Option B

4. Quick Check:

   Loop must stay within array bounds [OK]

Hint: Use i < arr.length to avoid out-of-bounds errors [OK]

Common Mistakes:

• Using <= instead of < in loop
• Starting XOR with 1 instead of 0
• Sorting array unnecessarily

5. Given the array [6, 1, 3, 6, 1, 5], which two numbers are the non-repeating elements found using the XOR method? Choose the correct pair.

hard

A. [3, 5]

B. [6, 1]

C. [1, 3]

D. [5, 6]

Solution

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

   6^1=7, 7^3=4, 4^6=2, 2^1=3, 3^5=6 (xor = 6).

2. Step 2: Find rightmost set bit and separate elements

   Rightmost set bit in 6 (binary 110) is bit 2 (value 2). Separate elements into two groups based on this bit and XOR each group to find unique numbers 3 and 5.

3. Final Answer:

   [3, 5] -> Option A

4. Quick Check:

   Unique elements are 3 and 5 [OK]

Hint: Use rightmost set bit to split and find unique numbers [OK]

Common Mistakes:

• Mixing up repeating and unique elements
• Not splitting array by set bit
• Incorrect XOR calculations