Two Non Repeating Elements in Array Using XOR in DSA Javascript - 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 that helps us identify these unique numbers without extra space. The method is efficient and works in linear time. It is useful when you want to quickly find two different numbers that appear only once.

Why it matters

Without this method, finding two unique numbers among duplicates would require extra memory or slower searching methods. This XOR approach solves the problem quickly and uses very little memory. It helps in real-world tasks like error detection, data analysis, and optimizing performance where speed and memory matter.

Where it fits

Before learning this, you should understand basic arrays and the XOR operation. After this, you can explore more complex bit manipulation problems and other unique element finding techniques.

Mental Model

Core Idea

Using XOR, we can combine all numbers to isolate the two unique ones by separating them based on differing bits.

Think of it like...

Imagine you have a box of socks where every sock has a matching pair except two unique socks. By shaking the box and sorting socks by color differences, you can separate and find those two unique socks without checking each one individually.

Array: [a, b, c, d, e, f, g, h]
Step 1: XOR all elements -> xor = a ^ b ^ c ^ d ^ e ^ f ^ g ^ h
Step 2: Find rightmost set bit in xor -> mask
Step 3: Divide elements into two groups based on mask bit
Group 1: Elements with bit set
Group 2: Elements with bit not set
Step 4: XOR each group separately to find unique elements
Result: unique1, unique2

Build-Up - 7 Steps

1

Foundation

Understanding XOR Basics

Concept: Learn what XOR does and its properties.

XOR (^) compares two bits and returns 1 if they are different, 0 if they are the same. Properties: - x ^ x = 0 (XOR with itself is zero) - x ^ 0 = x (XOR with 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 cancel out pairs of identical numbers to zero.

Understanding XOR's canceling property is key to isolating unique elements 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. Goal: Find 7 and 9 efficiently. Naive ways: Use extra memory or nested loops. Better way: Use XOR to find unique numbers without extra space.

Result

Problem clearly defined: find two unique numbers among duplicates.

Knowing the problem constraints helps choose the right XOR-based approach.

3

Intermediate

XOR All Elements to Find Combined XOR

🤔Before reading on: Do you think XORing all elements gives one unique number or a combination? Commit to your answer.

Concept: XOR all elements to get XOR of the two unique numbers combined.

XOR all array elements: result = num1 ^ num2 Since duplicates cancel out, only the XOR of the two unique numbers remains. 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

Result

Combined XOR of two unique numbers, e.g., 7 ^ 9 = 14 (1110 in binary).

XORing all elements reduces the problem to finding two numbers from their combined XOR.

4

Intermediate

Find Rightmost Set Bit to Separate Groups

🤔Before reading on: Do you think any set bit in combined XOR can separate the two unique numbers? Commit to your answer.

Concept: Find a bit where the two unique numbers differ to split the array into two groups.

Find rightmost set bit in combined XOR using: mask = xor & (-xor) This bit is 1 in one unique number and 0 in the other. Use this mask to divide array elements into two groups: - Group 1: Elements with this bit set - Group 2: Elements without this bit set Duplicates fall into same group and cancel out.

Result

Two groups formed, each containing one unique number and pairs that cancel out.

Separating numbers by differing bit isolates unique numbers into different groups.

5

Intermediate

XOR Each Group to Find Unique Numbers

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

For each group, XOR all elements: - Group 1 XOR result = unique number 1 - Group 2 XOR result = unique number 2 Example: Group 1: [7, 2, 2, 3, 3] XOR: 7 ^ 2 ^ 2 ^ 3 ^ 3 = 7 Group 2: [9] XOR: 9

Result

Two unique numbers found: 7 and 9.

XORing groups separately recovers unique numbers by canceling duplicates.

6

Advanced

Complete JavaScript Implementation

🤔Before reading on: Predict the output of the code for input [4, 1, 2, 1, 2, 5]. Commit to your answer.

Concept: Implement the full XOR-based solution in JavaScript.

function findTwoUnique(arr) { let xor = 0; for (const num of arr) { xor ^= num; } const mask = xor & (-xor); let num1 = 0, num2 = 0; for (const num of arr) { if ((num & mask) !== 0) { num1 ^= num; } else { num2 ^= num; } } return [num1, num2]; } const arr = [4, 1, 2, 1, 2, 5]; console.log(findTwoUnique(arr));

Result

[5, 4]

Seeing the full code connects theory to practice and confirms the approach works.

7

Expert

Why XOR Works for Two Unique Elements

🤔Before reading on: Do you think XOR can find more than two unique elements? Commit to your answer.

Concept: Understand the mathematical and bitwise reasoning behind XOR's effectiveness here.

XOR cancels pairs because x ^ x = 0. For two unique numbers a and b, xor = a ^ b. Finding a set bit in xor guarantees a and b differ there. Splitting array by this bit separates a and b into different groups. XORing each group cancels duplicates, leaving a or b. This method fails if more than two unique numbers exist because grouping by one bit can't separate all unique numbers.

Result

XOR method precisely isolates two unique numbers but not more.

Knowing XOR's limits prevents misuse and guides solving related problems.

Under the Hood

XOR operates bitwise, comparing each bit of numbers. When XORing all array elements, pairs cancel out to zero because identical bits XOR to zero. The remaining XOR is the combination of the two unique numbers. Finding a set bit in this XOR identifies a bit where these two numbers differ. Dividing numbers by this bit groups duplicates together, allowing XOR within groups to isolate each unique number.

Why designed this way?

This approach was designed to solve the problem in linear time and constant space, avoiding extra memory like hash maps. XOR's properties make it ideal for canceling pairs efficiently. Alternatives like sorting or hash tables use more time or space. The bitwise method is elegant and optimal for this specific problem.

Array elements
  ↓
XOR all elements
  ↓
Combined XOR (a ^ b)
  ↓
Find rightmost set bit (mask)
  ↓
Split elements into two groups by mask bit
  ↓           ↓
Group 1       Group 2
  ↓           ↓
XOR elements  XOR elements
  ↓           ↓
Unique a      Unique b

Myth Busters - 3 Common Misconceptions

Quick: Does XORing all elements give you the two unique numbers directly? Commit yes or no.

Common Belief: XORing all elements directly reveals the two unique numbers.

Reality: XORing all elements gives the XOR of the two unique numbers combined, not the numbers themselves.

Why it matters: Believing this leads to confusion and incorrect attempts to extract unique numbers without further steps.

Quick: Can this XOR method find three or more unique numbers in the array? Commit yes or no.

Common Belief: The XOR method works for any number of unique elements.

Reality: This XOR method only works for exactly two unique elements; it fails for three or more.

Why it matters: Using this method on more unique numbers results in wrong answers and wasted effort.

Quick: Does the position of the set bit chosen to split groups affect the correctness? Commit yes or no.

Common Belief: Any set bit in the combined XOR can be used to split groups correctly.

Reality: Only a set bit where the two unique numbers differ can separate them correctly; the rightmost set bit is a simple choice.

Why it matters: Choosing a wrong bit can fail to separate unique numbers, causing incorrect results.

Expert Zone

1

The choice of rightmost set bit is a simple heuristic; any set bit differing between the two unique numbers works, but rightmost is easiest to compute.

2

XOR's associative and commutative properties allow flexible grouping and ordering, which is why the method works regardless of array order.

3

This method can be extended to find one unique number when all others appear thrice by using bit counting, but that requires a different approach.

When NOT to use

Do not use this XOR method if there are more than two unique elements or if duplicates appear more than twice. Instead, use hash maps or sorting-based methods for those cases.

Production Patterns

This XOR technique is used in embedded systems and performance-critical code where memory is limited. It also appears in coding interviews to test bit manipulation skills and in error detection algorithms.

Connections

Bit Manipulation

Builds-on

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

Hash Tables

Alternative approach

Knowing XOR method helps appreciate when hash tables are needed and when bitwise tricks can replace extra memory.

Signal Processing

Similar pattern

XOR's canceling effect is analogous to noise cancellation in signals, where unwanted repeated patterns are removed to isolate unique signals.

Common Pitfalls

#1 Trying to find unique numbers by XORing all elements and returning the result directly.

Wrong approach:

function findUnique(arr) {
let xor = 0;
for (const num of arr) {
xor ^= num;
}
return xor; // Incorrect: returns combined XOR, not unique numbers
}

Correct approach:

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

Root cause:

Misunderstanding that XOR of all elements equals the two unique numbers directly, ignoring the need to separate groups.

#2 Using this XOR method on arrays with more than two unique elements.

Wrong approach:

const arr = [1, 2, 3, 2, 1, 4, 5];
// Using XOR method expecting to find three unique numbers (3,4,5)
// Code same as two unique numbers method

Correct approach:

Use a hash map or frequency count to find all unique elements when more than two exist.

Root cause:

Assuming the XOR method generalizes beyond two unique elements.

#3 Choosing a bit to split groups that is not set in the combined XOR or does not separate unique numbers.

Wrong approach:

const mask = 1 << 5; // Arbitrary bit not guaranteed to separate unique numbers

Correct approach:

const mask = xor & (-xor); // Rightmost set bit ensures correct separation

Root cause:

Not understanding the importance of selecting a differing bit between unique numbers.

Key Takeaways

XOR is a powerful bitwise operation that cancels out pairs of identical numbers, leaving only unique elements.

Finding two unique numbers among duplicates can be done efficiently by XORing all elements, then separating numbers by a differing bit.

The rightmost set bit in the combined XOR helps split the array into two groups, each containing one unique number.

This method works only when exactly two unique numbers exist and all others appear twice.

Understanding this approach deepens your grasp of bit manipulation and efficient problem solving without extra memory.

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