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.