Two Non Repeating Elements in Array Using XOR in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

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

intermediate

Why XOR of all elements in an array with exactly two non-repeating elements results in XOR of those two unique elements?

Because XOR of two same numbers is 0, all repeating elements cancel out, leaving XOR of only the two unique elements.

intermediate

How do you find a set bit in XOR of two unique numbers to separate them?

Find the rightmost set bit (bit with value 1) in the XOR result using expression: xor & (-xor). This bit differs between the two unique numbers.

intermediate

Explain the step to separate array elements into two groups using the set bit.

Divide elements into two groups: those with the set bit and those without. XOR each group separately to find the two unique numbers.

beginner

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

The time complexity is O(n) because we traverse the array a constant number of times.

What is the XOR of a number with itself?

A 0

B The number itself

C 1

D Undefined

XOR of a number with itself is always 0.

If XOR of all elements in an array is 6, what does this represent when exactly two elements are unique?

A Sum of two unique elements

B Product of two unique elements

C XOR of two unique elements

D Difference of two unique elements

The XOR of all elements equals XOR of the two unique elements after canceling duplicates.

How do you find the rightmost set bit in a number x?

A x & (-x)

B x | (-x)

C x & (x - 1)

D x ^ (-x)

x & (-x) isolates the rightmost set bit in x.

After finding the rightmost set bit, how are elements grouped?

A By even and odd values

B Randomly

C By greater or smaller than XOR value

D By presence or absence of the set bit

Elements are grouped based on whether the set bit is 1 or 0 in their binary form.

What is the main advantage of using XOR to find two unique elements?

A Uses extra memory

B Runs in O(n) time without extra space

C Runs in O(n^2) time

D Requires sorting

XOR method finds unique elements in linear time and constant space.

Describe the step-by-step process to find two non-repeating elements in an array using XOR.

Think about how XOR cancels duplicates and how to separate elements by a differing bit.

Explain why XOR operation helps in identifying unique elements in an array where all others repeat twice.

Focus on how XOR behaves with pairs and unique values.