0 to n.
Problem
You are given an arraynums containing n distinct numbers from the range [0, n]. Return the only number that is missing from the array.
The solution should run in
O(n) time and use O(1) extra space.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [3, 0, 1]Output
2[0, 3], which contains 0, 1, 2, 3. Since 2 is not present in the array, the missing number is 2.
Solution
We can solve this problem using bit manipulation and the XOR operation.The XOR operation has two important properties. When a number is XORed with itself, the result is
0, and when a number is XORed with 0, the result is the number itself.
Therefore, if we XOR all numbers from
0 to n with all elements of the array, every number that exists in the array will appear twice and cancel out. Only the missing number will remain.
For example, consider
nums = [3, 0, 1]:
0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1 = 2x ^ x = 0:
0 ^ 0 = 0
1 ^ 1 = 0
3 ^ 3 = 02 remains, which is the missing number.
We can efficiently perform this XOR operation while traversing the array. The result is initialized with
n, and each index and corresponding array value are XORed with it.
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int missing = n;
for (int i = 0; i < n; i++) {
// Matching numbers cancel each other using XOR.
missing ^= i ^ nums[i];
}
return missing;
}
}
Complexity
Each array element is processed once, resulting inO(n) time complexity. Only a constant number of variables is used, resulting in O(1) space complexity.