Find the Only Non Repeating Element Using XOR in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does XOR operation do when applied between two identical bits?

XOR of two identical bits is 0. For example, 1 XOR 1 = 0 and 0 XOR 0 = 0.

beginner

Why does XOR help find the only non-repeating element in a list where every other element repeats twice?

Because XOR of a number with itself is 0, all repeating elements cancel out, leaving only the non-repeating element after XORing all elements.

beginner

What is the initial value used when XORing all elements to find the non-repeating element?

The initial value is 0 because XOR with 0 leaves the number unchanged.

beginner

Given the list [2, 3, 2, 4, 4], what is the only non-repeating element found using XOR?

The only non-repeating element is 3.

beginner

Write the Python code snippet to find the only non-repeating element using XOR.

def find_non_repeating(arr): result = 0 for num in arr: result ^= num return result

What is the result of XOR between a number and 0?

A 1

B 0

C Undefined

D The number itself

XOR with 0 leaves the number unchanged.

If every element except one repeats twice, what will XOR of all elements give?

A Only the non-repeating element

B Product of all elements

C 0

D Sum of all elements

Repeating elements cancel out, leaving only the non-repeating element.

What is the time complexity of finding the non-repeating element using XOR?

A O(n)

B O(n^2)

C O(log n)

D O(1)

We scan the list once, so time complexity is linear.

Which of these properties of XOR is used in this problem?

A XOR is commutative and associative

B X XOR 0 = X

C All of the above

D X XOR X = 0

All these properties help in cancelling out duplicates and isolating the unique element.

What will be the output of find_non_repeating([5, 1, 5])?

A 5

B 1

C 0

D Error

5 XOR 1 XOR 5 = (5 XOR 5) XOR 1 = 0 XOR 1 = 1

Explain how XOR operation helps find the only non-repeating element in a list where every other element repeats twice.

Think about how pairs of same numbers behave with XOR.

Write a simple Python function to find the only non-repeating element using XOR and explain each step.

Start with 0 and XOR all elements one by one.