> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/268.-missing-number.md).

# 268. Missing Number

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?

```cpp
// Math
int missingNumber(vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size(), sum = 0;
    for (int num : nums) sum += num;
    return n * (n + 1) / 2 - sum;
}
```

```cpp
// XOR
int missingNumber(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0;
    for (int i = 0; i < nums.size(); ++i) {
        res ^= (i + 1) ^ nums[i];
    }
    return res;
}
```