Two Non Repeating Elements in Array Using XOR in DSA Typescript

Mental Model

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

Analogy: Imagine you have pairs of socks mixed in a drawer except two socks are unique. By comparing socks bit by bit, you separate the drawer into two piles so each unique sock ends up alone in a pile.

Array: [2, 3, 7, 9, 2, 3]
XOR all: 7 ^ 9 = ?
Split by bit: group1 -> 7, group2 -> 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

Step 1: XOR all elements to get xor_all

2 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3 = 14 (binary 1110)

Why: XOR cancels pairs, leaving XOR of unique numbers

Step 2: Find rightmost set bit in xor_all (14) to separate groups

rightmost set bit mask = 2 (binary 0010)

Why: This bit differs between the two unique numbers

Step 3: Divide array into two groups based on this bit and XOR each group

Group1 (bit set): 3, 7, 3
Group2 (bit not set): 2, 9, 2

Why: Each unique number falls into different groups

Step 4: XOR Group1 elements: 3 ^ 7 ^ 3 = 7

Group1 XOR = 7

Why: Pairs cancel out (3^3 = 0), leaving unique number 7

Step 5: XOR Group2 elements: 2 ^ 9 ^ 2 = 9

Group2 XOR = 9

Why: Pairs cancel out (2^2 = 0), leaving unique number 9

Result:

Unique numbers: 7 and 9

Annotated Code

DSA Typescript

class Solution {
  findTwoNonRepeating(arr: number[]): [number, number] {
    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 rightmost_set_bit = xor_all & (-xor_all);

    let num1 = 0;
    let num2 = 0;

    // Divide elements into two groups and XOR separately
    for (const num of arr) {
      if ((num & rightmost_set_bit) !== 0) {
        num1 ^= num; // XOR group where bit is set
      } else {
        num2 ^= num; // XOR group where bit is not set
      }
    }

    return [num1, num2];
  }
}

// Driver code
const arr = [2, 3, 7, 9, 2, 3];
const solution = new Solution();
const result = solution.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 combine pairs and keep XOR of unique numbers

const rightmost_set_bit = xor_all & (-xor_all);

Find rightmost set bit to separate two unique numbers

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

Divide numbers into two groups by bit and XOR each group to isolate unique numbers

Output

7 9

Complexity Analysis

Time: O(n) because we traverse the array a few times but each pass is linear

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Better than using hash maps which use O(n) space; XOR uses constant space and linear time

Edge Cases

Array with only two elements which are unique

Returns those two elements directly

DSA Typescript

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

Array where unique elements are the same number repeated once (invalid input)

Returns zero or incorrect result since problem assumes exactly two unique numbers

DSA Typescript

No explicit guard; problem assumption

Array with multiple pairs and two unique numbers at start or end

Algorithm still correctly finds unique numbers

DSA Typescript

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

When to Use This Pattern

When you see a problem asking to find two unique numbers among pairs, use XOR and bit manipulation to separate them efficiently.

Common Mistakes

Mistake: Not finding the rightmost set bit correctly and using wrong mask
Fix: Use xor_all & (-xor_all) to get the rightmost set bit reliably

Mistake: Not dividing numbers into two groups based on the set bit
Fix: Use bitwise AND with the mask to separate numbers into two groups before XOR

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 pairs efficiently.

The key insight is to XOR all numbers, find a differing bit, and split numbers into two groups to isolate each unique number.

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