Two Non Repeating Elements in Array Using XOR in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of XOR-based Two Non Repeating Elements Finder

What is the output of the following TypeScript code that finds two non-repeating elements in an array using XOR?

DSA Typescript

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

const result = findTwoNonRepeating([2, 3, 7, 9, 2, 3]);
console.log(result.sort((a,b) => a-b));

A [9, 7]

B [7, 9]

C [3, 7]

D [2, 3]

💡 Hint

Remember XOR of two identical numbers is zero, and XOR of zero with a number is the number itself.

The code uses XOR to find the XOR of all elements, which results in XOR of the two unique numbers. Then it finds a set bit to separate numbers into two groups and XORs each group to find the unique numbers. The output is the two unique numbers sorted ascending.

🧠 Conceptual

intermediate

Why XOR helps find two unique elements in an array?

Why does XOR operation help in finding two non-repeating elements in an array where all other elements repeat twice?

A Because XOR sorts the array and separates unique elements automatically.

B Because XOR adds all numbers together to find the sum of unique elements.

C Because XOR of two identical numbers is zero, so XORing all elements cancels out duplicates leaving XOR of unique elements.

D Because XOR multiplies all elements and unique elements remain as product.

💡 Hint

Think about what happens when you XOR a number with itself.

XOR of a number with itself is zero, so pairs cancel out. XOR of zero with a number is the number itself. This property helps isolate the XOR of the two unique elements.

🔧 Debug

advanced

Identify the error in XOR-based two unique elements code

What error does the following TypeScript code produce when trying to find two unique elements using XOR?

DSA Typescript

function findTwoUnique(arr: number[]): [number, number] {
  let xor = 0;
  for (let i = 0; i < arr.length; i++) {
    xor ^= arr[i];
  }
  const setBit = xor & -xor;
  let x = 0, y = 0;
  for (const num of arr) {
    if ((num & setBit) !== 0) {
      x ^= num;
    } else {
      y ^= num;
    }
  }
  return [x, y];
}

findTwoUnique([1, 2, 1, 3, 2, 5]);

A ReferenceError: xor is not defined

B SyntaxError: Unexpected token

C No error, returns [3, 5]

D TypeError: Cannot read property 'undefined' of undefined

💡 Hint

Check the loop boundary condition carefully.

The loop uses i <= arr.length which tries to access arr[arr.length], which is undefined, causing a TypeError when XORing undefined.

❓ Predict Output

advanced

Output of XOR partitioning step in two unique elements algorithm

What is the value of variables x and y after the partitioning loop in the following code snippet?

DSA Typescript

const arr = [4, 1, 2, 1, 2, 5];
let xor = 0;
for (const num of arr) {
  xor ^= num;
}
const setBit = xor & -xor;
let x = 0, y = 0;
for (const num of arr) {
  if ((num & setBit) !== 0) {
    x ^= num;
  } else {
    y ^= num;
  }
}
console.log([x, y]);

A [4, 5]

B [1, 2]

C [5, 4]

D [0, 0]

💡 Hint

The setBit separates numbers into two groups based on that bit.

The XOR of all elements is 4 ^ 5 = 1 (binary 0001). The rightmost set bit is 1. Partitioning by this bit groups numbers with that bit set and not set. XORing each group isolates 4 and 5.

🚀 Application

expert

Find two unique elements in large array efficiently

Given an array where all elements except two appear twice, which approach is the most efficient to find the two unique elements?

A Use XOR to find XOR of all elements, find a set bit, partition array, XOR partitions to find unique elements.

B Sort the array and scan to find elements that appear once.

C Use a hash map to count occurrences and pick elements with count 1.

D Use nested loops to compare each element with all others to find unique ones.

💡 Hint

Consider time and space complexity for large arrays.

Approach A uses bitwise XOR operations with O(n) time and O(1) space, making it efficient for large arrays. Other methods have higher time or space costs.

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