Find the Only Non Repeating Element Using XOR in DSA Typescript - Execution Trace

Concept Flow - Find the Only Non Repeating Element Using XOR

Start with result = 0

↓

For each element in array

↓

Apply XOR: result = result XOR element

↓

Repeat for all elements

↓

Result holds the non-repeating element

↓

Return result

We start with zero and XOR it with every element in the array. Pairs cancel out, leaving only the unique element.

Execution Sample

DSA Typescript

function findUnique(arr: number[]): number {
  let result = 0;
  for (const num of arr) {
    result ^= num;
  }
  return result;
}

This code finds the only element that does not repeat by XORing all elements.

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Visual State (XOR Result)
1	Initialize result	N/A	N/A	0	0
2	XOR with element	2	0	2	2
3	XOR with element	3	2	1	1
4	XOR with element	2	1	3	3
5	XOR with element	4	3	7	7
6	XOR with element	3	7	4	4
7	XOR with element	5	4	1	1
8	XOR with element	5	1	4	4
9	End of array	N/A	4	4	4

💡 All pairs XOR to zero, leaving the unique element 4 as the result.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
result	0	2	1	3	7	4	1	4	4

Key Moments - 3 Insights

Why does XORing pairs of the same number cancel out to zero?

Because XOR of a number with itself is zero, as shown in execution_table steps 4 and 6 where 2 XOR 2 and 3 XOR 3 cancel out.

Why do we start result with zero?

Zero is the identity for XOR, so XORing zero with any number returns that number, as seen in step 2.

What if the array has only one element?

The loop XORs zero with that element, so the result is that element itself, as the logic holds for single-element arrays.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'result' after XORing the third element?

A 2

B 3

C 1

D 0

💡 Hint

Check the 'Result After XOR' column at Step 3 in the execution_table.

At which step does the 'result' first become 0 after XOR operations?

A Step 4

B Never

C Step 6

D Step 8

💡 Hint

Look at the 'Result After XOR' column for all steps; zero never appears after initialization.

If the array was [1,1,2,2,3], what would be the final 'result' after all XORs?

A 3

B 0

C 1

D 2

💡 Hint

Pairs cancel out, leaving the unique element as the final result, similar to the example in execution_table.

Concept Snapshot

Find unique element by XORing all array elements.
XOR pairs cancel out to zero.
Start with result = 0.
XOR result with each element.
Final result is the non-repeating element.
Works in O(n) time and O(1) space.

Full Transcript

This concept uses XOR to find the only non-repeating element in an array. We start with a result variable set to zero. Then, for each element in the array, we XOR it with the result. Because XOR of a number with itself is zero, pairs cancel out. After processing all elements, the result holds the unique element. For example, in the array [2,3,2,4,3,5,5], pairs like 2 and 2, 3 and 3, 5 and 5 cancel out, leaving 4 as the unique element. This method is efficient and uses constant extra space.

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