Two Non Repeating Elements in Array Using XOR in DSA Typescript - Deep Dive

Overview - Two Non Repeating Elements in Array Using XOR

What is it?

This topic teaches how to find two unique numbers in an array where every other number repeats exactly twice. We use a special operation called XOR to do this efficiently without extra space. XOR helps us cancel out pairs and isolate the unique numbers. This method is faster and uses less memory than checking each number one by one.

Why it matters

Without this technique, finding unique numbers in large data sets would be slow and require extra memory to track counts. This XOR method solves the problem quickly and with minimal resources, which is important in real-world applications like error detection, data analysis, and embedded systems. It helps computers work smarter, not harder.

Where it fits

Before learning this, you should understand basic bitwise operations, especially XOR, and how arrays work. After this, you can explore more complex bit manipulation problems and optimization techniques in algorithms.

Mental Model

Core Idea

Using XOR cancels out pairs of identical numbers, leaving only the XOR of the two unique numbers, which we then separate by a differing bit.

Think of it like...

Imagine you have pairs of gloves mixed in a box, except two gloves are unique and don't have a pair. By shaking the box (XOR), all pairs cancel out, and only the two unique gloves remain. Then, by looking at a unique feature (like color), you separate these two gloves.

Array: [a, a, b, b, x, y]
Step 1: XOR all elements -> xor = x ^ y
Step 2: Find rightmost set bit in xor -> mask
Step 3: Divide elements into two groups by mask bit
Group 1: elements with bit set
Group 2: elements with bit not set
Step 4: XOR each group separately -> results are x and y

  ┌───────────────┐
  │ Array elements│
  └──────┬────────┘
         │ XOR all
         ▼
  ┌───────────────┐
  │ xor = x ^ y   │
  └──────┬────────┘
         │ Find rightmost set bit
         ▼
  ┌───────────────┐
  │ mask          │
  └──────┬────────┘
         │ Split array by mask bit
         ▼
  ┌───────────────┐      ┌───────────────┐
  │ Group 1       │      │ Group 2       │
  └──────┬────────┘      └──────┬────────┘
         │ XOR all             │ XOR all
         ▼                    ▼
      unique x             unique y

Build-Up - 7 Steps

1

Foundation

Understanding XOR Basics

Concept: Learn what XOR does and its key properties.

XOR (^) compares two bits and returns 1 if they are different, 0 if they are the same. For example, 1 ^ 1 = 0, 0 ^ 1 = 1. Important properties: - x ^ x = 0 (a number XOR itself is zero) - x ^ 0 = x (a number XOR zero is the number itself) - XOR is commutative and associative, so order doesn't matter. Example: 5 (0101) ^ 3 (0011) = 6 (0110)

Result

XOR helps us cancel out pairs of identical numbers because x ^ x = 0.

Understanding XOR's canceling property is the foundation for isolating unique numbers in arrays.

2

Foundation

Problem Setup: Array with Two Unique Numbers

Concept: Recognize the problem where all numbers repeat twice except two unique ones.

Given an array like [2, 3, 7, 9, 2, 3], numbers 7 and 9 appear once, others twice. The goal is to find these two unique numbers efficiently. Naive way: count occurrences using extra space. Better way: use XOR to exploit properties learned.

Result

We know XOR can cancel pairs, but with two unique numbers, XOR of whole array gives xor = x ^ y (two unique numbers XORed).

Identifying the problem clearly helps us apply XOR in a clever way to find two unique numbers.

3

Intermediate

Finding XOR of Two Unique Numbers

🤔Before reading on: If you XOR all numbers in the array, do you get one unique number or a combination? Commit to your answer.

Concept: XORing all elements results in XOR of the two unique numbers.

When you XOR all elements, pairs cancel out to zero, leaving xor = x ^ y where x and y are unique numbers. Example: Array: [2, 3, 7, 9, 2, 3] XOR all: 2 ^ 3 ^ 7 ^ 9 ^ 2 ^ 3 = (2 ^ 2) ^ (3 ^ 3) ^ 7 ^ 9 = 0 ^ 0 ^ 7 ^ 9 = 7 ^ 9 = xor

Result

xor = 7 ^ 9 = 14 (binary 1110)

Knowing that XOR of the entire array gives combined info about the two unique numbers is key to separating them.

4

Intermediate

Isolating a Differing Bit

🤔Before reading on: Do you think any bit set in xor must be different between the two unique numbers? Commit to yes or no.

Concept: Find a bit where the two unique numbers differ to separate them into groups.

Since xor = x ^ y, any bit set in xor means x and y differ at that bit. We find the rightmost set bit (mask) using: mask = xor & (-xor) This mask helps split numbers into two groups: - Group 1: numbers with this bit set - Group 2: numbers without this bit set Because x and y differ at this bit, they fall into different groups.

Result

mask = 2 (binary 0010) for xor=14 (1110) Groups split accordingly.

Finding a differing bit lets us separate the problem into two simpler XOR problems.

5

Intermediate

Separating and XORing Groups

Concept: XOR numbers in each group to find the unique numbers separately.

For each group, XOR all numbers: - Group 1 XOR gives one unique number - Group 2 XOR gives the other unique number Example: Group 1 (bit set): 2, 2, 3, 3 Group 2 (bit not set): 7, 9 XOR Group 1: 2 ^ 2 ^ 3 ^ 3 = 0 XOR Group 2: 7 ^ 9 = 14 But since 7 and 9 differ at mask bit, they split differently in actual example. Correct grouping yields unique numbers.

Result

Two unique numbers found: 7 and 9

Separating by differing bit and XORing groups isolates each unique number cleanly.

6

Advanced

Complete TypeScript Implementation

🤔Before reading on: Do you think this algorithm uses extra space proportional to input size? Commit yes or no.

Concept: Implement the full algorithm in TypeScript with clear comments.

function findTwoUnique(arr: number[]): [number, number] { let xor = 0; for (const num of arr) { xor ^= num; // XOR all elements } const mask = xor & -xor; // rightmost set bit let x = 0, y = 0; for (const num of arr) { if ((num & mask) !== 0) { x ^= num; // XOR group with bit set } else { y ^= num; // XOR group without bit set } } return [x, y]; } // Example usage const arr = [2, 3, 7, 9, 2, 3]; const result = findTwoUnique(arr); console.log(result);

Result

[7, 9]

Knowing the algorithm uses constant extra space and linear time is crucial for efficient solutions.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: Can this method handle negative numbers and zeros correctly? Commit yes or no.

Concept: Understand how the algorithm behaves with negative numbers, zeros, and large inputs.

The XOR operation works on bits, so negative numbers (two's complement) and zero are handled naturally. Edge cases: - Array with zeros: zeros cancel out like any other number. - Negative numbers: XOR works the same way. - Large arrays: algorithm runs in O(n) time and O(1) space. Performance: - No extra data structures needed. - Only two passes through the array. This makes it suitable for memory-constrained environments.

Result

Algorithm correctly returns unique numbers even with negatives and zeros.

Understanding bitwise operations on signed integers prevents bugs in real-world usage.

Under the Hood

The XOR operation compares bits of numbers. When XORing pairs, identical bits cancel out to zero. XORing the entire array leaves the XOR of the two unique numbers. Finding the rightmost set bit in this XOR identifies a bit where the two unique numbers differ. Splitting the array by this bit groups numbers so that each unique number is isolated in one group. XORing each group cancels pairs and reveals the unique number.

Why designed this way?

This method was designed to solve the problem in linear time without extra memory. Traditional counting methods require extra space or multiple passes. Bitwise XOR exploits mathematical properties to cancel duplicates efficiently. The choice of the rightmost set bit is a simple way to split numbers based on difference, avoiding complex data structures.

Input Array
  │
  ▼
XOR all elements
  │
  ▼
xor = x ^ y (two unique numbers XORed)
  │
  ▼
Find rightmost set bit (mask)
  │
  ▼
Split array into two groups by mask bit
  ├─────────────┬─────────────┤
  │             │             │
Group 1       Group 2       
  │             │             │
XOR all in    XOR all in    
Group 1       Group 2       
  │             │             │
  ▼             ▼             ▼
unique x      unique y      Pairs canceled

Myth Busters - 3 Common Misconceptions

Quick: Does XORing the entire array give you one unique number or two combined? Commit your answer.

Common Belief: XORing the array will directly give one unique number.

Reality: XORing the array gives the XOR of the two unique numbers combined, not the individual numbers.

Why it matters: Assuming you get one unique number leads to wrong conclusions and incorrect algorithms.

Quick: Can you separate the two unique numbers by any bit set in xor? Commit yes or no.

Common Belief: Any set bit in xor can be used to separate the two unique numbers.

Reality: Only bits where the two unique numbers differ are set in xor, so any set bit works, but choosing the rightmost set bit is simplest and efficient.

Why it matters: Choosing bits incorrectly can complicate the algorithm or cause errors.

Quick: Does this method require extra memory proportional to input size? Commit yes or no.

Common Belief: You need extra memory like hash maps to find unique numbers.

Reality: This XOR method uses constant extra space, no additional data structures needed.

Why it matters: Misunderstanding space complexity leads to inefficient solutions.

Expert Zone

1

The choice of rightmost set bit is a neat trick because it isolates the lowest differing bit, simplifying grouping.

2

XOR operations are very fast at the hardware level, making this approach highly efficient for large data sets.

3

This method naturally extends to finding one unique number when all others repeat twice, showing its versatility.

When NOT to use

This method only works when exactly two numbers are unique and all others appear exactly twice. If more unique numbers exist or counts differ, use hash maps or sorting-based methods instead.

Production Patterns

Used in embedded systems and low-memory environments for error detection and data integrity checks. Also common in coding interviews to test bit manipulation skills.

Connections

Bitwise Operations

Builds-on

Mastering XOR here deepens understanding of bitwise operations, which are fundamental in low-level programming and optimization.

Hash Maps

Alternative approach

Knowing XOR method helps appreciate space-time tradeoffs compared to hash maps for counting occurrences.

Error Detection Codes (Parity Bits)

Similar pattern

XOR's canceling property is the basis for parity bits in error detection, linking algorithms to communication systems.

Common Pitfalls

#1 Assuming XOR of entire array gives one unique number directly.

Wrong approach:

let xor = 0;
for (const num of arr) {
xor ^= num;
}
return xor; // expecting one unique number

Correct approach:

let xor = 0;
for (const num of arr) {
xor ^= num;
}
const mask = xor & -xor;
let x = 0, y = 0;
for (const num of arr) {
if ((num & mask) !== 0) x ^= num;
else y ^= num;
}
return [x, y];

Root cause:

Misunderstanding that XOR of two unique numbers is a combined value, not a single unique number.

#2 Using a random bit instead of rightmost set bit to split groups.

Wrong approach:

const mask = 1 << 5; // arbitrary bit
// then split groups by mask

Correct approach:

const mask = xor & -xor; // rightmost set bit
// split groups by mask

Root cause:

Not knowing the significance of the rightmost set bit leads to incorrect grouping.

#3 Trying to use this method when more than two unique numbers exist.

Wrong approach:

Applying same XOR splitting logic on array with 3+ unique numbers.

Correct approach:

Use hash maps or sorting for multiple unique numbers.

Root cause:

Assuming the algorithm generalizes beyond its problem constraints.

Key Takeaways

XOR cancels out pairs of identical numbers, leaving combined XOR of unique numbers.

Finding the rightmost set bit in XOR helps separate two unique numbers into distinct groups.

XORing each group isolates the unique numbers efficiently without extra memory.

This method works in linear time and constant space, ideal for large data sets.

Understanding bitwise operations deeply enables solving complex problems elegantly.

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