Find the Only Non Repeating Element Using XOR in DSA Typescript - Deep Dive

Overview - Find the Only Non Repeating Element Using XOR

What is it?

This topic teaches how to find the single element in a list that does not repeat, while all other elements appear twice. We use a special operation called XOR to do this efficiently. XOR compares bits of numbers and helps us cancel out pairs, leaving only the unique number. This method is fast and uses little extra space.

Why it matters

Without this method, finding the unique element would require extra memory or slower searching through the list multiple times. This XOR trick solves the problem quickly and simply, which is important in real-world tasks like error detection, data analysis, or optimizing software performance. It shows how clever math can simplify complex problems.

Where it fits

Before learning this, you should understand basic programming concepts like loops, arrays, and bitwise operations. After this, you can explore other bitwise tricks, or learn about hash maps and sets for finding unique elements in different ways.

Mental Model

Core Idea

XORing all numbers cancels out pairs and leaves only the unique number.

Think of it like...

Imagine you have pairs of socks in a drawer, except one sock is missing its pair. If you take one sock from each pair and put them in a pile, all pairs cancel out, leaving only the single unmatched sock.

Array: [a, b, a, c, b]
XOR process:
Start with 0
0 XOR a = a
 a XOR b = a⊕b
(a⊕b) XOR a = b (because a⊕a=0)
b XOR c = b⊕c
(b⊕c) XOR b = c (because b⊕b=0)
Result = c (unique element)

Build-Up - 7 Steps

1

Foundation

Understanding XOR Operation Basics

Concept: Learn what XOR does with bits and numbers.

XOR (exclusive OR) compares two bits: if they are different, result is 1; if same, result is 0. For example, 5 (0101) XOR 3 (0011) = 6 (0110). XOR has special properties: a XOR a = 0 and a XOR 0 = a.

Result

Knowing XOR basics lets you see how pairs cancel out when XORed.

Understanding XOR's canceling property is key to solving problems with pairs efficiently.

2

Foundation

Problem Setup: Identifying Unique Element

Concept: Define the problem of finding the single non-repeating element in a list.

Given an array where every element appears twice except one, find that unique element. For example, in [2, 3, 2], 3 is unique. The challenge is to do this without extra memory or slow searching.

Result

Clear problem statement helps focus on efficient solutions.

Knowing the problem constraints guides us to use XOR instead of brute force.

3

Intermediate

Applying XOR to Cancel Pairs

🤔Before reading on: do you think XORing all elements will give the unique element or something else? Commit to your answer.

Concept: Use XOR on all elements to cancel out pairs and isolate the unique number.

XOR all elements in the array one by one. Since XOR of a number with itself is zero, pairs vanish. XOR with zero leaves the number unchanged. So, after processing all elements, only the unique element remains.

Result

The final XOR result is the unique element.

Knowing XOR's properties lets us solve the problem in one pass without extra space.

4

Intermediate

Implementing XOR Solution in TypeScript

🤔Before reading on: do you think the XOR solution needs extra arrays or variables? Commit to your answer.

Concept: Write code that uses XOR to find the unique element efficiently.

const findUnique = (arr: number[]): number => { let result = 0; for (const num of arr) { result ^= num; // XOR accumulates } return result; }; // Example usage: console.log(findUnique([2, 3, 2])); // Output: 3

Result

Output: 3

Implementing XOR in code shows how simple and efficient this approach is.

5

Intermediate

Dry Run: XOR Step-by-Step Example

🤔Before reading on: predict the XOR result after each step for [4, 1, 2, 1, 2]. Commit to your answer.

Concept: Walk through XOR operations step-by-step to see how pairs cancel.

Array: [4, 1, 2, 1, 2] Start result = 0 Step 1: 0 XOR 4 = 4 Step 2: 4 XOR 1 = 5 Step 3: 5 XOR 2 = 7 Step 4: 7 XOR 1 = 6 Step 5: 6 XOR 2 = 4 Final result = 4 (unique element)

Result

Unique element found is 4

Stepwise XOR helps visualize how pairs vanish and unique remains.

6

Advanced

Handling Edge Cases and Limitations

🤔Before reading on: do you think XOR works if more than one element is unique? Commit to your answer.

Concept: Understand when XOR method works and when it fails.

XOR method only works if exactly one element is unique and all others appear twice. If multiple unique elements exist or counts differ, XOR won't isolate a single number. Also, XOR works on integers, not complex data types.

Result

XOR method is limited to specific problem constraints.

Knowing limits prevents misuse and guides choosing correct algorithms.

7

Expert

XOR in Production: Performance and Memory Benefits

🤔Before reading on: do you think XOR solution uses less memory than hash maps? Commit to your answer.

Concept: Explore why XOR is preferred in performance-critical systems.

XOR solution uses constant extra memory (one variable) and runs in linear time. Hash maps or sets require extra memory proportional to input size. In embedded systems or large data streams, XOR is ideal for speed and low memory. It also avoids overhead of data structures.

Result

XOR is a highly efficient, low-memory solution for this problem.

Understanding XOR's efficiency helps choose it for real-world, resource-limited applications.

Under the Hood

XOR compares bits of two numbers. When XORing a number with itself, all bits cancel to zero. XORing zero with a number returns the number unchanged. By XORing all elements, pairs cancel out, leaving only the unique element's bits set. This works because XOR is associative and commutative, so order doesn't matter.

Why designed this way?

XOR was designed as a bitwise operation for digital logic and error detection. Its properties naturally fit problems involving pairs and uniqueness. Alternatives like hash maps use more memory and slower lookups. XOR offers a minimal, elegant solution leveraging hardware-level operations.

Input Array: [x, y, x, z, y]

Step 1: result = 0
Step 2: result = 0 XOR x = x
Step 3: result = x XOR y = x⊕y
Step 4: result = (x⊕y) XOR x = y (since x⊕x=0)
Step 5: result = y XOR z = y⊕z
Step 6: result = (y⊕z) XOR y = z (since y⊕y=0)

Final result = z (unique element)

Myth Busters - 3 Common Misconceptions

Quick: Does XOR find unique elements if multiple elements appear once? Commit yes or no.

Common Belief: XOR can find unique elements even if more than one element is unique.

Reality: XOR only isolates a single unique element when all others appear exactly twice. Multiple unique elements cause XOR to combine them, not separate.

Why it matters: Using XOR incorrectly leads to wrong answers and bugs in programs expecting multiple unique values.

Quick: Does XOR work on strings or complex objects? Commit yes or no.

Common Belief: XOR can be used directly on any data type like strings or objects.

Reality: XOR works only on numbers at the bit level. Non-numeric types must be converted or handled differently.

Why it matters: Misapplying XOR on unsupported types causes errors or meaningless results.

Quick: Does XOR require sorting the array first? Commit yes or no.

Common Belief: The array must be sorted before applying XOR to find the unique element.

Reality: XOR works regardless of order because it is associative and commutative.

Why it matters: Sorting wastes time and resources unnecessarily if XOR is used properly.

Expert Zone

1

XOR's associative and commutative properties mean the order of elements doesn't affect the result, enabling single-pass solutions.

2

In hardware and embedded systems, XOR is a native CPU instruction, making this method extremely fast and low power.

3

XOR can be extended to find two unique elements appearing once when others appear twice, but requires more complex bit manipulation.

When NOT to use

Do not use XOR if multiple unique elements exist or if elements appear more than twice. Instead, use hash maps, frequency counts, or sorting-based methods for those cases.

Production Patterns

XOR is used in error detection codes, cryptography, and embedded systems for quick uniqueness checks. It is also common in coding interviews to test understanding of bitwise operations and optimization.

Connections

Hash Maps for Frequency Counting

Alternative method to find unique elements by counting occurrences.

Understanding XOR helps appreciate memory-efficient solutions compared to hash maps that use extra space.

Parity Bits in Error Detection

XOR operation is the basis for parity bits used to detect errors in data transmission.

Knowing XOR's role in error detection shows its practical importance beyond algorithms.

Set Theory in Mathematics

XOR corresponds to symmetric difference operation in sets, highlighting a mathematical foundation.

Connecting XOR to set operations deepens understanding of its logical behavior.

Common Pitfalls

#1 Assuming XOR works when multiple unique elements exist.

Wrong approach:

const findUnique = (arr: number[]): number => {
let result = 0;
for (const num of arr) {
result ^= num;
}
return result;
};
// Input: [1, 2, 3, 2, 1, 4]
// Output: 7 (incorrect)

Correct approach:

// Use hash map or frequency count for multiple unique elements
const findUniques = (arr: number[]): number[] => {
const freq = new Map();
for (const num of arr) {
freq.set(num, (freq.get(num) || 0) + 1);
}
return Array.from(freq.entries()).filter(([_, count]) => count === 1).map(([num]) => num);
};
// Output: [3, 4]

Root cause:

Misunderstanding XOR's limitation to exactly one unique element.

#2 Trying to XOR strings directly.

Wrong approach:

const result = 'a' ^ 'b'; // NaN or unexpected result

Correct approach:

Convert strings to char codes before XOR:
const result = 'a'.charCodeAt(0) ^ 'b'.charCodeAt(0);

Root cause:

Not knowing XOR operates on numbers at bit level.

#3 Sorting array before XOR unnecessarily.

Wrong approach:

arr.sort();
let result = 0;
for (const num of arr) {
result ^= num;
}

Correct approach:

let result = 0;
for (const num of arr) {
result ^= num;
}

Root cause:

Not realizing XOR's order independence.

Key Takeaways

XOR operation cancels out pairs of identical numbers, leaving the unique number when applied to the entire list.

This method finds the single non-repeating element efficiently in one pass using constant extra space.

XOR only works correctly if exactly one element is unique and all others appear twice.

Understanding XOR's bitwise properties unlocks many clever algorithmic solutions beyond this problem.

Misusing XOR outside its limits leads to incorrect results, so knowing when and how to apply it is crucial.

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