Find the Only Non Repeating Element Using XOR in DSA Javascript

Mental Model

XORing a number with itself cancels it out to zero, so XORing all numbers leaves only the one that appears once.

Analogy: Imagine you have pairs of socks in a drawer. If you take out all socks and pair them up, only the single unmatched sock remains visible.

Array: [2, 3, 2, 4, 3]
XOR process: 0 ⊕ 2 -> 2
2 ⊕ 3 -> 1
1 ⊕ 2 -> 3
3 ⊕ 4 -> 7
7 ⊕ 3 -> 4
Result: 4 (only non-repeating)

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3]

Goal: Find the single number that does not repeat in the array

Step 1: Start with result = 0, XOR with first element 2

result = 0 ⊕ 2 = 2

Why: Initialize result with first XOR operation

Step 2: XOR result with next element 3

result = 2 ⊕ 3 = 1

Why: Combine next number to cancel duplicates later

Step 3: XOR result with next element 2

result = 1 ⊕ 2 = 3

Why: XOR with duplicate 2 cancels one 2 out

Step 4: XOR result with next element 4

result = 3 ⊕ 4 = 7

Why: Add new number 4 to result

Step 5: XOR result with last element 3

result = 7 ⊕ 3 = 4

Why: XOR with duplicate 3 cancels one 3 out, leaving 4

Result:

Final result = 4 (only non-repeating element)

Annotated Code

DSA Javascript

class Solution {
  findNonRepeating(arr) {
    let result = 0;
    for (const num of arr) {
      result ^= num; // XOR current result with num
    }
    return result;
  }
}

// Driver code
const sol = new Solution();
const input = [2, 3, 2, 4, 3];
const output = sol.findNonRepeating(input);
console.log(output);

result ^= num; // XOR current result with num

XOR accumulates all numbers, cancelling duplicates

Output

4

Complexity Analysis

Time: O(n) because we traverse the array once to XOR all elements

Space: O(1) because we use only one variable to store the XOR result

vs Alternative: Compared to using a hash map to count frequencies (O(n) time and O(n) space), XOR uses constant space and is faster

Edge Cases

Array with only one element

Returns that single element as it is the only non-repeating one

DSA Javascript

No special guard needed; XOR with 0 returns the element itself

Array where all elements repeat except one

Correctly returns the single non-repeating element

DSA Javascript

XOR operation inherently handles this case

Empty array

Returns 0 as no elements to XOR

DSA Javascript

No explicit guard; result initialized to 0

When to Use This Pattern

When you see a problem asking for the single unique element among duplicates, reach for the XOR pattern because it cancels pairs efficiently.

Common Mistakes

Mistake: Starting XOR result with the first element instead of 0
Fix: Initialize result to 0 to ensure all elements are XORed correctly

Mistake: Using addition or other operations instead of XOR
Fix: Use XOR (^) because it cancels duplicates perfectly

Summary

Finds the single non-repeating element in an array where all others repeat.

Use when you need to identify one unique number among pairs efficiently.

XORing all elements cancels duplicates, leaving only the unique element.

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