## 题目描述

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

Example 1

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

Example 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?

## 解法一

### Python

``````class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for i in range(0, len(nums)):
result ^= i
result ^= nums[i]
result ^= len(nums)
return result``````

### Java

``````public class Solution {
public int missingNumber(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
result ^= i;
result ^= nums[i];
}
result ^= nums.length;
return result;
}
}``````

### C++

``````class Solution {
public:
int missingNumber(vector<int> &nums) {
int result = 0;
for (int i = 0; i < nums.size(); i++) {
result ^= i;
result ^= nums[i];
}
result ^= nums.size();
return result;
}
};``````