Two Non Repeating Elements in Array Using XOR in DSA Javascript

Mental Model

Use XOR to cancel out pairs and isolate two unique numbers by splitting based on a differing bit.

Analogy: Imagine you have pairs of socks mixed in a drawer, except two socks have no pair. By checking a unique feature (like color stripe), you separate socks into two groups and find the unmatched ones easily.

Array: [2, 3, 7, 9, 2, 3]
Unique elements: 7 and 9
XOR all: 2 ⊕ 3 ⊕ 7 ⊕ 9 ⊕ 2 ⊕ 3 = 7 ⊕ 9 = 14 (1110)
Split by rightmost set bit of XOR result:
Group 1 (bit set): [7] -> 7
Group 2 (bit not set): [2, 3, 9, 2, 3] -> 9

Dry Run Walkthrough

Input: array: [2, 3, 7, 9, 2, 3]

Goal: Find the two numbers that appear only once (7 and 9) using XOR operations

Step 1: XOR all elements to get xor_all = 7 ⊕ 9 = 14

xor_all = 14 (binary 1110)

Why: XOR cancels out pairs, leaving XOR of two unique numbers

Step 2: Find rightmost set bit in xor_all (14) -> bit_mask = 2 (binary 0010)

bit_mask = 2

Why: This bit differs between the two unique numbers, helps split array

Step 3: Divide array into two groups based on bit_mask: Group 1 (bit set): [7] Group 2 (bit not set): [2, 3, 9, 2, 3]

Group 1: [7]
Group 2: [2, 3, 9, 2, 3]

Why: Separating elements ensures unique numbers fall into different groups

Step 4: XOR elements in Group 1 -> 7 = 7

Group 1 XOR = 7

Why: Pairs cancel out, leaving the unique number 7

Step 5: XOR elements in Group 2 -> 2 ⊕ 3 ⊕ 9 ⊕ 2 ⊕ 3 = 9

Group 2 XOR = 9

Why: Pairs cancel out, leaving the unique number 9

Step 6: num1 = Group 1 XOR = 7 (one unique number)

num1 = 7

Why: XOR within each group isolates the unique number

Step 7: num2 = Group 2 XOR = 9 (other unique number)

num2 = 9

Why: XOR within each group isolates the unique number

Result:

Unique elements are 7 and 9

Annotated Code

DSA Javascript

class Solution {
  findTwoNonRepeating(arr) {
    let xor_all = 0;
    for (const num of arr) {
      xor_all ^= num; // XOR all elements to get xor of two unique numbers
    }

    // Find rightmost set bit in xor_all
    const bit_mask = xor_all & (-xor_all);

    let num1 = 0, num2 = 0;
    for (const num of arr) {
      if ((num & bit_mask) !== 0) {
        num1 ^= num; // XOR group with bit set
      } else {
        num2 ^= num; // XOR group without bit set
      }
    }

    return [num1, num2];
  }
}

// Driver code
const arr = [2, 3, 7, 9, 2, 3];
const sol = new Solution();
const result = sol.findTwoNonRepeating(arr);
console.log(result[0] + ' ' + result[1]);

xor_all ^= num; // XOR all elements to get xor of two unique numbers

XOR all array elements to isolate XOR of two unique numbers

const bit_mask = xor_all & (-xor_all);

Find rightmost set bit to split numbers into two groups

if ((num & bit_mask) !== 0) { num1 ^= num; } else { num2 ^= num; }

Divide elements into two groups and XOR separately to find unique numbers

return [num1, num2];

Return the two unique numbers found

Output

7 9

Complexity Analysis

Time: O(n) because we traverse the array a few times but only linearly

Space: O(1) because we use only a few variables, no extra arrays

vs Alternative: Naive approach uses nested loops or hash maps with O(n) time and O(n) space; XOR method is more space efficient

Edge Cases

Array with only two elements (both unique)

Returns those two elements correctly

DSA Javascript

xor_all ^= num; // XOR all elements to get xor of two unique numbers

Array where unique elements are equal (impossible scenario)

Function returns zeroes or incorrect result, but problem constraints prevent this

DSA Javascript

const bit_mask = xor_all & (-xor_all);

Array with multiple duplicates and exactly two unique elements

Correctly finds the two unique elements

DSA Javascript

if ((num & bit_mask) !== 0) { num1 ^= num; } else { num2 ^= num; }

When to Use This Pattern

When you see a problem asking to find exactly two unique numbers among duplicates, think of XOR splitting by a differing bit to separate and find them efficiently.

Common Mistakes

Mistake: Not finding the rightmost set bit correctly, causing wrong grouping
Fix: Use bit_mask = xor_all & (-xor_all) to isolate the rightmost set bit

Mistake: XORing all elements into one variable but not splitting into two groups
Fix: Split elements into two groups based on the set bit and XOR separately

Summary

Finds two unique numbers in an array where all others appear twice using XOR.

Use when you need to find exactly two non-repeating elements among duplicates efficiently.

The key insight is to use XOR to isolate differing bits and split the array into two groups to find unique numbers.

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