Missing Number (XOR/Sum)
Find the missing number in an array containing n distinct numbers from the range [0, n]. Given n numbers from 0 to n with one missing, identify the missing one. Two elegant O(n) time, O(1) space solutions: (1) XOR approach using cancellation property, (2) Mathematical sum formula. Both avoid sorting and extra space, making them optimal for this problem.
Visualization
Interactive visualization for Missing Number (XOR/Sum)
Missing Number (XOR Method)
XOR Result: 0
Array (range 0..3, one number missing):
• Time: O(n)
• Space: O(1)
• Alternative: sum formula or XOR
Interactive visualization with step-by-step execution
Implementation
1function missingNumber(nums: number[]): number {
2 const n = nums.length;
3 let missing = n;
4
5 for (let i = 0; i < n; i++) {
6 missing ^= i ^ nums[i];
7 }
8
9 return missing;
10}
11
12// Alternative: sum formula
13function missingNumberSum(nums: number[]): number {
14 const n = nums.length;
15 const expectedSum = (n * (n + 1)) / 2;
16 const actualSum = nums.reduce((a, b) => a + b, 0);
17 return expectedSum - actualSum;
18}Deep Dive
Theoretical Foundation
Missing Number has two optimal approaches: **XOR Method**: XOR all indices [0,n] with all array values. Present numbers cancel (a⊕a=0), missing number remains. Works because XOR is associative and commutative. **Sum Method**: Expected sum = n(n+1)/2 (Gauss formula), actual sum = sum of array. Missing = expected - actual. XOR is safer from integer overflow. Both O(n) time, O(1) space. The problem is solvable in one pass without sorting because we know the exact range and count.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Packet loss detection in networking
Database sequence gap detection
File integrity checking
Manufacturing serial number validation
Attendance tracking systems
Interview algorithm problems
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.