Find the Only Non Repeating Element Using XOR in DSA Python - 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

↓

After all elements processed

↓

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 Python

arr = [2, 3, 2, 4, 4]
result = 0
for num in arr:
    result ^= num
print(result)

This code finds the only element that does not repeat in the array using XOR.

Execution Table

Step	Operation	Current Element	Result Before XOR	Result After XOR	Explanation
1	Initialize result	N/A	N/A	0	Start with result = 0
2	XOR with element	2	0	2	0 XOR 2 = 2
3	XOR with element	3	2	1	2 XOR 3 = 1
4	XOR with element	2	1	3	1 XOR 2 = 3
5	XOR with element	4	3	7	3 XOR 4 = 7
6	XOR with element	4	7	3	7 XOR 4 = 3
7	End of array	N/A	3	3	Result is 3, the non-repeating element

💡 All elements processed; pairs canceled out leaving only the unique element 3.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
result	0	2	1	3	7	3	3
current element	N/A	2	3	2	4	4	N/A

Key Moments - 3 Insights

Why does XORing pairs of the same number cancel out?

Because XOR of a number with itself is 0, as shown in steps 5 and 6 where 4 XOR 4 returns to 3 (previous result).

Why start result with 0?

XOR with 0 returns the number itself, so starting with 0 ensures the first element sets the initial result (step 2).

What if the array has more than one non-repeating element?

This method only works if exactly one element is unique; otherwise, the result will be XOR of all unique elements, not a single one.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'result' after processing the third element?

A 2

B 3

C 1

D 7

💡 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 operation?

A Step 2

B Never

C Step 4

D Step 6

💡 Hint

Look at the 'Result After XOR' column for all steps; see if 0 appears.

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

A 2

B 1

C 3

D 0

💡 Hint

Pairs cancel out; only 2 is unique. Refer to how pairs cancel in the execution table.

Concept Snapshot

Find unique element using XOR:
- Initialize result = 0
- XOR result with each array element
- Pairs cancel out (x XOR x = 0)
- Result holds the only non-repeating element
- Works only if exactly one unique element exists

Full Transcript

To find the only non-repeating element in an array, start with a result variable set to zero. Then XOR this result with each element of the array one by one. Because XOR of a number with itself is zero, all repeating elements cancel out. After processing all elements, the result contains the unique element. This method is efficient and uses constant extra space. It works only if there is exactly one element that does not repeat.

Practice

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

easy

A. It returns the number itself

B. It returns 0

C. It returns 1

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 B

4. Quick Check:

   5 ^ 5 = 0 [OK]

Hint: XOR same numbers always zeroes out [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to find the XOR of all elements in a list arr in Python?

easy

A. result = 0
for num in arr:
result |= num

B. result = 0
for num in arr:
result = result + num

C. result = 0
for num in arr:
result ^= num

D. result = 1
for num in arr:
result *= num

Solution

1. Step 1: Initialize result to 0 for XOR operation

   Start with 0 because XOR with 0 returns the number itself.

2. Step 2: Use ^= operator to XOR each element

   Loop through each number and XOR it with the result to accumulate the XOR of all elements.

3. Final Answer:

   result = 0 for num in arr: result ^= num -> Option C

4. Quick Check:

   Use ^= for XOR accumulation [OK]

Hint: Use ^= operator inside loop for XOR accumulation [OK]

Common Mistakes:

• Using + instead of ^
• Starting result with 1
• Using |= instead of ^=

3. What is the output of the following code?

arr = [2, 3, 5, 4, 5, 3, 4]
result = 0
for num in arr:
    result ^= num
print(result)

medium

A. 2

B. 5

C. 0

D. 4

Solution

1. Step 1: XOR all elements step-by-step

   Start with result=0. XOR with 2 -> 2, XOR with 3 -> 1, XOR with 5 -> 4, XOR with 4 -> 0, XOR with 5 -> 5, XOR with 3 -> 6, XOR with 4 -> 2.

2. Step 2: Final XOR value is the non-repeating element

   The final result after XORing all elements is 2, which appears only once.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Only 2 is non-repeating, XOR result = 2 [OK]

Hint: XOR all elements; result is unique number [OK]

Common Mistakes:

• Not XORing all elements
• Confusing output with repeated numbers
• Assuming sum instead of XOR

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

def find_unique(arr):
    result = 1
    for num in arr:
        result ^= num
    return result

print(find_unique([1, 2, 2, 1, 3]))

medium

A. The XOR operator should be replaced with +

B. The loop should start from index 1, not 0

C. The function should return sum instead of XOR

D. result should be initialized to 0, not 1

Solution

1. Step 1: Check initialization of result

   Result must start at 0 because XOR with 0 returns the number itself. Starting at 1 changes the result incorrectly.

2. Step 2: Verify loop and XOR usage

   The loop and XOR operator are correct; only initialization is wrong.

3. Final Answer:

   result should be initialized to 0, not 1 -> Option D

4. Quick Check:

   Initialize XOR accumulator with 0 [OK]

Hint: Start XOR accumulator with 0, not 1 [OK]

Common Mistakes:

• Starting result at 1
• Replacing XOR with addition
• Changing loop range incorrectly

5. Given an array where every element appears twice except one element which appears once, how can you find the unique element efficiently using XOR? Choose the best approach.

hard

A. Initialize result to 0 and XOR it with every element in the array

B. Sort the array and find the element that does not have a duplicate next to it

C. Use a dictionary to count occurrences and find the element with count 1

D. Add all elements and subtract twice the sum of unique elements

Solution

1. Step 1: Use XOR properties for pairs

   XOR of two identical numbers is 0, so pairs cancel out when XORed.

2. Step 2: XOR all elements starting from 0

   Starting with 0, XOR all elements leaves only the unique element because pairs vanish.

3. Step 3: Compare with other methods

   Sorting or dictionary methods work but are less efficient in time or space.

4. Final Answer:

   Initialize result to 0 and XOR it with every element in the array -> Option A

5. Quick Check:

   XOR all elements starting at 0 for unique element [OK]

Hint: XOR all elements starting at 0 to find unique [OK]

Common Mistakes:

• Using sorting which is slower
• Using extra space with dictionary
• Incorrect arithmetic approach