Find the missing number in an array containing n distinct numbers from the range [0, n] using XOR bit manipulation. This elegant solution leverages the property that XOR is self-inverse: a ^ a = 0.
Bit Manipulation Array Math LeetCode 268 ↗ EasyGiven: An array nums containing n distinct numbers in the range [0, n]
Return: The only number in the range that is missing from the array
Example:
[3,0,1] → Output: 2[0,1] → Output: 2[9,6,4,2,3,5,7,0,1] → Output: 8fun missingNumber(nums: IntArray): Int {
var result = nums.size for (i in nums.indices) { result = result xor i xor nums[i] } return result
}The XOR operation has special properties that make this solution elegant:
a ^ a = 0 (any number XOR'd with itself equals 0)a ^ 0 = a (any number XOR'd with 0 equals itself)a ^ b = b ^ a (order doesn't matter)By XORing all indices [0, n] with all array values, pairs that exist in both cancel out (become 0), leaving only the missing number.
result = n (the length of the array)i from 0 to n-1:
result with the index iresult with the array value nums[i]result contains the missing numberWhy it works: We XOR all numbers from 0 to n (both as indices and including n itself) with all values in the array. Numbers that appear in both cancel out, leaving only the missing one.
For array [3, 0, 1] (missing 2):
result = 3 (length)
i=0: result = 3 ^ 0 ^ 3 = 0
i=1: result = 0 ^ 1 ^ 0 = 1
i=2: result = 1 ^ 2 ^ 1 = 2 ← Missing number!
Breakdown: (0^1^2^3) ^ (3^0^1) = 2
All pairs cancel except 2Single pass through the array with only a single variable for the result. This is more efficient than the sum formula approach when dealing with very large numbers (avoids potential integer overflow in some languages).
missing = n*(n+1)/2 - sum(nums) — O(n) time, O(1) space, but may overflowThe XOR approach is optimal: O(n) time, O(1) space, and no overflow concerns.