Missing Number

Desicription

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

1
2
Input: [3,0,1]
Output: 2

Example 2:

1
2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Solution

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = nums.size();
for(int i = 0; i < nums.size(); i++) {
res ^= i;
res ^= nums[i];
}
return res;
}
};