Fundamental Algorithms8 sections · 291 units
Open in Course

Single Number - XOR Properties

XOR has two key properties: 1.1. a⊕a=0a \oplus a = 0 (self-inverse).

2.2. a⊕0=aa \oplus 0 = a (identity).

XOR all elements. Pairs cancel out (a⊕a=0a \oplus a = 0), leaving only the unique element.

Example: 4⊕1⊕2⊕1⊕2=4⊕(1⊕1)⊕(2⊕2)=4⊕0⊕0=44 \oplus 1 \oplus 2 \oplus 1 \oplus 2 = 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2) = 4 \oplus 0 \oplus 0 = 4.