Two Non Repeating Elements in Array Using XOR in DSA Javascript - Time & Space Complexity

Time Complexity: Two Non Repeating Elements in Array Using XOR

O(n)

Understanding Time Complexity

We want to understand how the time needed grows when finding two unique numbers in an array using XOR.

How does the number of steps change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds two numbers that appear only once in an array where all others appear twice, using XOR operations.

Identify Repeating Operations

• Primary operation: Two separate loops over the array to XOR elements.
• How many times: Each loop runs once over all elements, so twice in total.

How Execution Grows With Input

Each element is processed twice, so the total steps grow directly with the number of elements.

Input Size (n)	Approx. Operations
10	About 20 XOR checks
100	About 200 XOR checks
1000	About 2000 XOR checks

Pattern observation: Operations increase linearly as input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the two unique numbers grows in direct proportion to the array size.

Common Mistake

[X] Wrong: "Because there are two loops, the time is O(n²)."

[OK] Correct: The loops run one after another, not nested, so total steps add up, not multiply.

Interview Connect

Understanding this linear time approach shows you can handle problems efficiently by using bitwise operations and careful looping.

Self-Check

"What if the array had three unique numbers instead of two? How would the time complexity change?"

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