Two Non Repeating Elements in Array Using XOR in DSA Typescript - Build from Scratch

Two Non Repeating Elements in Array Using XOR

📖 Scenario: Imagine you have a list of numbers where every number appears twice except for two unique numbers that appear only once. You want to find those two unique numbers quickly without using extra space.

🎯 Goal: Build a TypeScript program that finds the two non-repeating elements in an array using the XOR operation.

📋 What You'll Learn

Create an array called numbers with the exact values: [2, 3, 7, 9, 2, 3, 9, 11]

Create a variable called xorAll and initialize it to 0

Use a for loop with variable num to XOR all elements in numbers and store the result in xorAll

Find the rightmost set bit in xorAll and store it in a variable called rightmostSetBit

Create two variables num1 and num2 initialized to 0

Use a for loop with variable num to separate numbers into two groups based on rightmostSetBit and XOR each group to find the two unique numbers

Print the two unique numbers num1 and num2 separated by a space

💡 Why This Matters

🌍 Real World

Finding unique items in large datasets quickly, such as detecting unique error codes or unique user IDs in logs.

💼 Career

This technique is useful for software engineers working on performance-critical applications, embedded systems, or data processing pipelines.

1

Create the array of numbers

Create an array called numbers with these exact values: [2, 3, 7, 9, 2, 3, 9, 11]

DSA Typescript

# Your code here

Hint

Use const numbers = [2, 3, 7, 9, 2, 3, 9, 11]; to create the array.

2

Initialize XOR accumulator

Create a variable called xorAll and set it to 0

DSA Typescript

const numbers = [2, 3, 7, 9, 2, 3, 9, 11];
# Your code here

Hint

Use let xorAll = 0; to start XOR accumulation.

3

XOR all elements to find combined XOR

Use a for loop with variable num to XOR all elements in numbers and store the result in xorAll

DSA Typescript

const numbers = [2, 3, 7, 9, 2, 3, 9, 11];
let xorAll = 0;
# Your code here

Hint

Use for (const num of numbers) and inside the loop do xorAll ^= num;

4

Find rightmost set bit and separate groups

Create a variable called rightmostSetBit and set it to xorAll & (-xorAll). Then create variables num1 and num2 initialized to 0. Use a for loop with variable num to XOR numbers into num1 if (num & rightmostSetBit) !== 0, else XOR into num2

DSA Typescript

const numbers = [2, 3, 7, 9, 2, 3, 9, 11];
let xorAll = 0;
for (const num of numbers) {
    xorAll ^= num;
}
# Your code here

Hint

Use const rightmostSetBit = xorAll & (-xorAll); to find the bit. Then separate numbers using a loop and XOR into num1 and num2.

5

Print the two unique numbers

Write a console.log statement to print num1 and num2 separated by a space

DSA Typescript

const numbers = [2, 3, 7, 9, 2, 3, 9, 11];
let xorAll = 0;
for (const num of numbers) {
    xorAll ^= num;
}
const rightmostSetBit = xorAll & (-xorAll);
let num1 = 0;
let num2 = 0;
for (const num of numbers) {
    if ((num & rightmostSetBit) !== 0) {
        num1 ^= num;
    } else {
        num2 ^= num;
    }
}
# Your code here

Hint

Use console.log(num1 + " " + num2); to print the two unique numbers separated by a space.

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