Find the Only Non Repeating Element Using XOR in DSA Javascript - Execution Trace

Concept Flow - Find the Only Non Repeating Element Using XOR

Start with result = 0

↓

Take next element from array

↓

Apply XOR: result = result XOR element

↓

More elements?

Yes→Repeat XOR step

No↓

Result holds the non-repeating element

↓

End

We start with zero and XOR it with each element in the array one by one. Because XOR of two same numbers is zero, all repeating elements cancel out, leaving only the unique element.

Execution Sample

DSA Javascript

const arr = [2, 3, 5, 4, 5, 3, 4];
let result = 0;
for (const num of arr) {
  result ^= num;
}
console.log(result);

This code finds the only non-repeating element in the array using XOR.

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Visual State (XOR Result)
1	Initialize result	N/A	N/A	0	result = 0
2	XOR with element	2	0	2	0 ^ 2 = 2
3	XOR with element	3	2	1	2 ^ 3 = 1
4	XOR with element	5	1	4	1 ^ 5 = 4
5	XOR with element	4	4	0	4 ^ 4 = 0
6	XOR with element	5	0	5	0 ^ 5 = 5
7	XOR with element	3	5	6	5 ^ 3 = 6
8	XOR with element	4	6	2	6 ^ 4 = 2
9	End of array	N/A	2	2	Final result = 2

💡 All repeating elements cancel out, leaving 2 as the only non-repeating element.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
result	0	2	1	4	0	5	6	2	2
current element	N/A	2	3	5	4	5	3	4	N/A

Key Moments - 3 Insights

Why does XORing a number with itself result in zero?

Because XOR compares bits and returns 0 when bits are the same. So, any number XOR itself cancels out to zero, as shown in step 5 where result XOR 4 becomes 0.

Why do we start with result = 0?

Starting with zero means the first XOR operation just returns the first element itself, as zero XOR any number is that number (step 2). This initializes the result correctly.

How does XOR help find the unique element when others repeat?

Repeated elements XOR to zero because each pair cancels out. Only the unique element remains after XORing all elements, as seen in the final result 2 in step 9.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'result' after XORing with the third element?

A 4

B 5

C 1

D 2

💡 Hint

Check row 3 in the execution_table where current element is 3 and result after XOR is shown.

At which step does the 'result' become zero during the XOR process?

A Step 6

B Step 5

C Step 4

D Step 8

💡 Hint

Look for rows where 'Result After XOR' is zero in the execution_table.

If the array had no repeating elements, what would the final 'result' be?

A XOR of all elements

B Sum of all elements

C 0

D First element

💡 Hint

Recall that XOR accumulates all elements; without repeats, no cancellation happens.

Concept Snapshot

Find unique element using XOR:
- Initialize result = 0
- XOR result with each array element
- Repeated elements cancel out (x ^ x = 0)
- Final result is the unique element
- Works in O(n) time and O(1) space

Full Transcript

This concept uses XOR to find the only non-repeating element in an array. We start with result = 0 and XOR it with each element. Because XOR of a number with itself is zero, all repeating elements cancel out. The final result after processing all elements is the unique element. The execution table shows step-by-step how result changes after each XOR operation. Key moments clarify why XOR cancels pairs and why we start with zero. The visual quiz tests understanding of intermediate results and the XOR behavior.

Practice

1. What does the XOR operation do when applied between two identical numbers?

easy

A. It returns 0

B. It returns the number itself

C. It returns 1

D. It returns the sum of the numbers

Solution

1. Step 1: Understand XOR property for identical numbers

   XOR of a number with itself always results in 0 because bits cancel out.

2. Step 2: Apply XOR to example

   For example, 5 ^ 5 = 0 as each bit is the same and cancels.

3. Final Answer:

   It returns 0 -> Option A

4. Quick Check:

   X ^ X = 0 [OK]

Hint: XOR same numbers always zeroes out [OK]

Common Mistakes:

• Thinking XOR returns the number itself
• Confusing XOR with OR operation
• Assuming XOR sums numbers

2. Which of the following is the correct syntax to XOR two variables a and b in JavaScript?

easy

A. a && b

B. a ^ b

C. a xor b

D. a | b

Solution

1. Step 1: Recall JavaScript bitwise XOR operator

   In JavaScript, the XOR operator is represented by the caret symbol ^.

2. Step 2: Check each option

   a ^ b uses ^ correctly. a xor b uses 'xor' which is not valid syntax. Options A and D are logical AND and bitwise OR respectively.

3. Final Answer:

   a ^ b -> Option B

4. Quick Check:

   Use ^ for XOR in JavaScript [OK]

Hint: Use ^ symbol for XOR in JavaScript [OK]

Common Mistakes:

• Using 'xor' keyword
• Confusing XOR with && or ||
• Using | instead of ^

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

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

medium

A. 2

B. 0

C. 4

D. 3

Solution

1. Step 1: XOR all elements in the array

   Start with result = 0, then XOR with each element: 0 ^ 2 = 2, 2 ^ 3 = 1, 1 ^ 2 = 3, 3 ^ 4 = 7, 7 ^ 3 = 4.

2. Step 2: Final XOR result is the non-repeating element

   The only element that does not repeat is 4, which is the final XOR result.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Final XOR = 4 [OK]

Hint: XOR all numbers; result is unique element [OK]

Common Mistakes:

• Not starting XOR from 0
• XORing incorrectly in loop
• Assuming sum instead of XOR

4. Identify the error in the following code that tries to find the non-repeating element using XOR:

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

medium

A. Variable 'result' is not initialized to 0

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

C. XOR operator is incorrect, should be &&

D. Array should be sorted before XOR

Solution

1. Step 1: Check initialization of 'result'

   The variable 'result' is declared but not initialized, so it is undefined initially.

2. Step 2: Effect of uninitialized 'result' on XOR

   XOR with undefined results in NaN, so the final output will be incorrect. Initializing 'result' to 0 fixes this.

3. Final Answer:

   Variable 'result' is not initialized to 0 -> Option A

4. Quick Check:

   Initialize result = 0 before XOR loop [OK]

Hint: Always initialize XOR accumulator to 0 [OK]

Common Mistakes:

• Not initializing XOR variable
• Using wrong loop condition
• Misusing XOR operator

5. Given an array where every element appears three times except one element which appears once, can XOR be used directly to find the unique element? Why or why not?

hard

A. Yes, but only if the array length is odd

B. Yes, XOR works for any number of repetitions

C. No, because XOR requires sorted arrays

D. No, because XOR only cancels pairs of identical numbers

Solution

1. Step 1: Understand XOR behavior with repeated elements

   XOR cancels out pairs of identical numbers because x ^ x = 0.

2. Step 2: Analyze effect of triply repeated elements

   Elements repeated thrice do not cancel out with XOR because XOR of three identical numbers is the number itself, not zero.

3. Step 3: Conclusion on XOR usage

   Therefore, XOR alone cannot find the unique element if others repeat thrice; other methods are needed.

4. Final Answer:

   No, because XOR only cancels pairs of identical numbers -> Option D

5. Quick Check:

   XOR cancels pairs, not triples [OK]

Hint: XOR cancels pairs only, not triples [OK]

Common Mistakes:

• Assuming XOR works for any repetition count
• Thinking sorting helps XOR
• Confusing XOR with sum or count