Find the Only Non Repeating Element Using XOR in DSA Typescript

Mental Model

XORing a number with itself cancels out to zero, so XORing all numbers leaves only the one that appears once.

Analogy: Imagine you have pairs of socks in a drawer. If you take out all socks and pair them up, only the single unmatched sock remains alone.

Array: [2, 3, 2, 4, 3]
XOR process: 0 ⊕ 2 ⊕ 3 ⊕ 2 ⊕ 4 ⊕ 3 = 4

Dry Run Walkthrough

Input: array: [2, 3, 2, 4, 3]

Goal: Find the single number that does not repeat in the array

Step 1: Start with result = 0, XOR with 2

result = 0 ⊕ 2 = 2

Why: Initialize result with first number to start cancellation

Step 2: XOR result with 3

result = 2 ⊕ 3 = 1

Why: Combine next number to cancel duplicates later

Step 3: XOR result with 2

result = 1 ⊕ 2 = 3

Why: Second 2 cancels first 2 partially

Step 4: XOR result with 4

result = 3 ⊕ 4 = 7

Why: Include unique number 4

Step 5: XOR result with 3

result = 7 ⊕ 3 = 4

Why: Second 3 cancels first 3, leaving only 4

Result:

Final result = 4

Annotated Code

DSA Typescript

class Solution {
  findSingle(arr: number[]): number {
    let result = 0;
    for (const num of arr) {
      result ^= num; // XOR current number with result to cancel duplicates
    }
    return result; // result holds the single non-repeating number
  }
}

const sol = new Solution();
const input = [2, 3, 2, 4, 3];
const output = sol.findSingle(input);
console.log(output);

result ^= num; // XOR current number with result to cancel duplicates

XOR accumulates cancellation of pairs, leaving only the unique number

return result; // result holds the single non-repeating number

Return the final XOR result which is the unique element

Output

4

Complexity Analysis

Time: O(n) because we traverse the array once to XOR all elements

Space: O(1) because we use only one variable to store the XOR result

vs Alternative: Compared to using a hash map to count frequencies (O(n) time and O(n) space), XOR uses less memory and is faster

Edge Cases

Array with only one element

Returns that element as it is the only one

DSA Typescript

for (const num of arr) {

Array where all elements except one appear twice

Correctly returns the single non-repeating element

DSA Typescript

result ^= num;

Empty array

Returns 0 as no elements to XOR

DSA Typescript

let result = 0;

When to Use This Pattern

When you see a problem asking for a single unique element among duplicates, reach for the XOR pattern because it cancels pairs efficiently.

Common Mistakes

Mistake: Starting XOR result with the first array element instead of 0
Fix: Initialize result with 0 to handle empty arrays and simplify logic

Mistake: Using addition or subtraction instead of XOR
Fix: Use XOR operator (^) because it cancels duplicates correctly

Summary

Finds the single non-repeating element in an array where all others repeat twice.

Use when you need to identify a unique number among pairs efficiently.

XORing all numbers cancels duplicates and leaves the unique number.

Practice

1. What does the XOR operation do when applied between two identical numbers?

easy

A. It returns 1

B. It returns the number itself

C. It returns 0

D. It returns the sum of the numbers

Solution

1. Step 1: Understand XOR property for identical numbers

   XOR of a number with itself always results in 0 because bits cancel out.

2. Step 2: Apply XOR to example

   For example, 5 XOR 5 = 0.

3. Final Answer:

   It returns 0 -> Option C

4. Quick Check:

   X XOR X = 0 [OK]

Hint: XOR of same numbers is always zero [OK]

Common Mistakes:

• Thinking XOR returns the number itself
• Confusing XOR with OR or AND
• Assuming XOR sums the numbers

2. Which of the following TypeScript code snippets correctly initializes a variable to zero for XOR operation?

easy

A. let result = 1;

B. let result = 0;

C. let result = null;

D. let result = undefined;

Solution

1. Step 1: Identify correct initial value for XOR

   For XOR operations, starting with 0 is correct because 0 XOR any number returns that number.

2. Step 2: Check code snippets

   Only let result = 0; correctly initializes for XOR accumulation.

3. Final Answer:

   let result = 0; -> Option B

4. Quick Check:

   Initial XOR value = 0 [OK]

Hint: Start XOR with zero to keep numbers unchanged [OK]

Common Mistakes:

• Starting XOR with 1 instead of 0
• Using null or undefined which cause errors
• Not initializing the variable

3. What is the output of the following TypeScript code?

const arr = [2, 3, 2, 4, 3];
let result = 0;
for (const num of arr) {
  result ^= num;
}
console.log(result);

medium

A. 3

B. 0

C. 2

D. 4

Solution

1. Step 1: XOR all elements in the array

   Calculate stepwise: 0 XOR 2 = 2, 2 XOR 3 = 1, 1 XOR 2 = 3, 3 XOR 4 = 7, 7 XOR 3 = 4.

2. Step 2: Identify the non-repeating element

   All repeating numbers cancel out, leaving 4 as the only non-repeating element.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Result after XOR = 4 [OK]

Hint: XOR all numbers; duplicates cancel out [OK]

Common Mistakes:

• Not XORing all elements
• Confusing output with last element
• Assuming sum instead of XOR

4. Identify the error in this TypeScript code that tries to find the only non-repeating element using XOR:

const arr = [1, 2, 1, 3, 2];
let result;
for (let i = 0; i < arr.length; i++) {
  result ^= arr[i];
}
console.log(result);

medium

A. Variable 'result' is not initialized

B. Loop condition is incorrect

C. XOR operator is used wrongly

D. Array is empty

Solution

1. Step 1: Check variable initialization

   The variable 'result' is declared but not initialized, so it is undefined initially.

2. Step 2: Understand XOR with undefined

   XOR with undefined causes NaN or runtime error; it must start at 0.

3. Final Answer:

   Variable 'result' is not initialized -> Option A

4. Quick Check:

   Initialize result = 0 before XOR loop [OK]

Hint: Always initialize XOR accumulator to zero [OK]

Common Mistakes:

• Forgetting to initialize result
• Assuming undefined XOR number works
• Incorrect loop boundaries

5. Given an array where every element repeats twice except one element which repeats thrice, can XOR alone find the unique element? Why?

const arr = [5, 5, 5, 7, 7, 8, 8];

hard

A. No, XOR fails because it only cancels pairs, not triples

B. Yes, XOR works because duplicates cancel out

C. Yes, but only if array is sorted

D. No, XOR works only for arrays with all unique elements

Solution

1. Step 1: Understand XOR behavior with odd counts

   XOR cancels even appearances (like twice) to 0, but leaves the result of odd appearances (like thrice: x ^ x ^ x = 0, not x).

2. Step 2: Analyze the given array

   5 appears thrice (odd), 7 and 8 twice (even); XOR of all yields 0, so XOR alone cannot find the unique element repeated thrice.

3. Final Answer:

   No, XOR fails because it only cancels pairs, not triples -> Option A

4. Quick Check:

   XOR fails to find element repeated thrice [OK]

Hint: XOR cancels pairs, fails for triples [OK]

Common Mistakes:

• Thinking XOR works for triples
• Believing sorting is required for XOR
• Confusing XOR with requiring exactly one unique