Single Number (XOR)

Find the element that appears only once by XOR-ing every number. Duplicate pairs cancel to 0, revealing the unique value.

Time: O(n)Space: O(1)XOR Trick

4[0]

1[1]

2[2]

1[3]

2[4]

acc (0)

new acc (0)

FastSlowStep 1 / 0

Question 1/3

Why does XOR-ing all elements find the single non-repeated number?

Accumulator0

Binary00000000

Elements processed0 / 5

a ^ a= 0 (cancels)

a ^ 0= a (identity)

a ^ b= b ^ a (commutative)

(a^b)^c= a^(b^c)

DSAverse

Bit Manipulation

Loading Bit Manipulation...

Binary Register

bit 15bit 0