Single Number (XOR Trick)
Find the single element that appears exactly once in an array where every other element appears exactly twice. The elegant solution uses XOR's self-inverse property (a⊕a=0) to cancel out pairs in O(n) time with O(1) space. This is a classic demonstration of XOR's power in solving constraint optimization problems and is frequently asked in coding interviews.
Visualization
Interactive visualization for Single Number (XOR Trick)
Single Number (XOR Trick)
Current XOR Result: 0
Array (every element appears twice except one):
• Time: O(n)
• Space: O(1)
• Uses XOR bit manipulation
Interactive visualization with step-by-step execution
Implementation
1function singleNumber(nums: number[]): number {
2 let result = 0;
3 for (const num of nums) {
4 result ^= num;
5 }
6 return result;
7}Deep Dive
Theoretical Foundation
Single Number exploits XOR mathematical properties: (1) a⊕a=0 makes pairs cancel, (2) a⊕0=a preserves single element, (3) commutativity and associativity allow any processing order. Algorithm: XOR all elements together. Each pair (x,x) cancels to 0, and 0⊕single=single. Result is the unique element. Time: O(n) single pass. Space: O(1) constant. This is optimal as we must examine all elements. Extension: for 'all appear 3 times except one', use bit counting modulo 3.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Finding corrupted/missing data in paired systems
RAID parity calculations
Interview algorithm problems
Data integrity checks
Network packet duplicate detection
Database consistency checks
Use Cases
Related Algorithms
Count Set Bits (Brian Kernighan's Algorithm)
Efficiently count the number of 1 bits (set bits) in the binary representation of an integer. Brian Kernighan's algorithm is one of the most elegant bit manipulation techniques, invented by Brian Kernighan (co-author of 'The C Programming Language'). The algorithm repeatedly clears the rightmost set bit, making it optimal as it only loops for the number of set bits rather than all bits.
Check if Power of Two
Determine if a given integer is a power of 2 using a brilliant single bitwise operation. Powers of 2 in binary have exactly one set bit: 1=0001, 2=0010, 4=0100, 8=1000, 16=10000. This unique property enables an O(1) constant-time check using the elegant formula: n > 0 && (n & (n-1)) == 0. This trick is widely used in systems programming, memory management, and optimization.
XOR Operations Collection
Comprehensive collection of XOR (exclusive OR) bit manipulation techniques with unique mathematical properties: a ⊕ a = 0 (self-inverse), a ⊕ 0 = a (identity), commutative, and associative. XOR is fundamental in finding unique/missing elements, in-place swapping, parity checking, cryptography, error detection, and many optimization problems. These elegant properties make XOR one of the most powerful bitwise operators.
Reverse Bits
Reverse the bit pattern of a 32-bit unsigned integer efficiently using bit manipulation. For example, 43261596 (binary: 00000010100101000001111010011100) becomes 964176192 (binary: 00111001011110000010100101000000) after reversal. This operation is critical in Fast Fourier Transform (FFT) bit-reversal permutation, graphics processing, cryptographic operations, and understanding little-endian/big-endian conversions at the bit level.