Total Accepted: 74080
Total Submissions: 174115
Difficulty: Medium
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n
, find the one that is missing from the array.
For example,Given nums = [0, 1, 3]
return 2
.
Note:Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
public int missingNumber(int[] nums) {
/* Ref:
1.https://leetcode.com/discuss/58647/line-simple-java-bit-manipulate-solution-with-explaination
2. https://leetcode.com/discuss/56174/3-different-ideas-xor-sum-binary-search-java-code
The basic idea is to use XOR operation. We all know that a^b^b =a, which means two xor operations with the same number will eliminate the number and reveal the original number.
In this solution, I apply XOR operation to both the index and value of the array. In a complete array with no missing numbers, the index and value should be perfectly corresponding( nums[index] = index), so in a missing array, what left finally is the missing number.
*/
int xor = 0, i = 0;
for (i=0; i<nums.length; i++) {
xor = xor ^ i ^ nums[i];
}
return xor ^ i;
}
