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

↓

Result: Two unique non-repeating elements

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

Execution Sample

DSA Typescript

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 non-repeating 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 of 14	14	2 (binary 10)	-	-	-
8	Group pass 1: num=2 (&2!=0) x=0^2=2	-	2	2	0	X:[2]
9	Group pass: num=3 (&2!=0) x=2^3=1	-	2	1	0	X:[2,3]
10	Group pass: num=7 (&2!=0) x=1^7=6	-	2	6	0	X:[2,3,7]
11	Group pass: num=9 (&2==0) y=0^9=9	-	2	6	9	X:[2,3,7]; Y:[9]
12	Group pass: num=2 (&2!=0) x=6^2=4	-	2	4	9	X:[2,3,7,2]; Y:[9]
13	Group pass: num=3 (&2!=0) x=4^3=7	-	2	7	9	X:[2,3,7,2,3]; Y:[9]
14	All elements processed	-	2	7	9	X complete; Y complete
15	Result: Unique elements are 7 (X) and 9 (Y)	-	-	7	9	[7,9]
16	End	-	-	7	9	Completed

💡 All elements processed, two unique non-repeating elements found as 7 and 9.

Variable Tracker

Variable	Start	After Step 6	After Step 7	After Step 15
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 before splitting into groups?

XORing all elements gives XOR of the two unique numbers combined (step 6 in execution_table). This helps find a bit that differs between them to split the array.

How do we find the rightmost set bit in the XOR result?

We use xor & (-xor) (step 7). This isolates the rightmost set bit, which helps divide numbers into two groups.

Why do we 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 different groups, allowing separate XOR to find them (steps 8-13).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the XOR value after processing all elements?

A 13

B 14

C 15

D 7

💡 Hint

Check the 'XOR Value' column at step 6 in execution_table.

At which step do we find the rightmost set bit in the XOR result?

A Step 7

B Step 5

C Step 10

D Step 14

💡 Hint

Look for the step mentioning 'Find rightmost set bit' in execution_table.

If the set bit was different (another differing bit), how would the group XOR results change?

A Group XOR values would be zero

B Group XOR values would be completely different unique numbers

C Group X and Y XOR values would be swapped

D Group XOR values would remain the same

💡 Hint

Different set bits (e.g., bit 3 instead of bit 1) would swap which group each unique number falls into, swapping x and y.

Concept Snapshot

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

Full Transcript

This concept finds two unique non-repeating elements in an array where all others repeat twice. First, XOR all elements to get combined XOR of the two unique numbers. Then find the rightmost set bit in this XOR result to split the array into two groups. Each group contains one unique number and duplicates. XORing each group separately reveals the two unique numbers. This method uses bitwise operations efficiently with linear time and constant space.

Practice

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

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 unique ones

D. To reverse the array elements

Solution

1. Step 1: Understand XOR properties

   XOR of two same numbers is 0, and XOR with 0 is the number itself.

2. Step 2: Apply XOR on array elements

   XORing all elements cancels out repeating ones, leaving XOR of two unique elements.

3. Final Answer:

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

4. Quick Check:

   XOR cancels duplicates = isolate unique elements [OK]

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

Common Mistakes:

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

2. Which of the following TypeScript code snippets correctly initializes the XOR variable to start finding two unique elements?

easy

A. let xor = 1;

B. let xor = 0;

C. let xor = -1;

D. let xor = null;

Solution

1. Step 1: Identify initial XOR value

   XOR with 0 returns the number itself, so start with 0.

2. Step 2: Confirm initialization

   Initializing xor as 0 allows proper XOR accumulation over array elements.

3. Final Answer:

   let xor = 0; -> Option B

4. Quick Check:

   Start XOR with 0 for correct accumulation [OK]

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

Common Mistakes:

• Starting XOR with 1 changes results
• Using null or undefined causes errors
• Starting XOR with -1 gives wrong output

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

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

medium

A. 0

B. 9

C. 7

D. 14

Solution

1. Step 1: XOR all elements in 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 all elements is 14.

3. Final Answer:

   14 -> Option D

4. Quick Check:

   XOR all elements = 14 [OK]

Hint: XOR all elements stepwise to find final value [OK]

Common Mistakes:

• Stopping XOR early
• Incorrect XOR calculation order
• Confusing XOR with addition

4. Identify the error in this TypeScript code snippet that tries to find two unique 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. Loop condition should be i < arr.length, not i <= arr.length

B. XOR operator should be & instead of ^

C. Variable xor should be initialized to 1

D. Array elements should be converted to strings before XOR

Solution

1. Step 1: Check loop boundary

   Loop uses i <= arr.length which causes out-of-bounds access at last iteration.

2. Step 2: Correct loop condition

   Change to i < arr.length to avoid accessing undefined element.

3. Final Answer:

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

4. Quick Check:

   Loop index must be less than array length [OK]

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

Common Mistakes:

• Using wrong loop boundary causing runtime error
• Confusing XOR with AND operator
• Initializing xor incorrectly

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

hard

A. [3, 5]

B. [6, 1]

C. [1, 3]

D. [5, 6]

Solution

1. Step 1: XOR all elements

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

2. Step 2: Find rightmost set bit of XOR

   Rightmost set bit of 6 (binary 110) is 2 (binary 010).

3. Step 3: Divide elements into two groups and XOR separately

   Group 1 (bit set): 6, 3, 6 -> XOR = 3; Group 2 (bit not set): 1, 1, 5 -> XOR = 5.

4. Final Answer:

   [3, 5] -> Option A

5. Quick Check:

   Two unique elements = [3, 5] [OK]

Hint: Use rightmost set bit to separate and XOR groups [OK]

Common Mistakes:

• Not separating elements by set bit
• Mixing order of unique elements
• Incorrect XOR calculations