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

# Missing Number

## Description

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?

## Solutions

### My solution

Idea: if `nums[i] > 0`, mark its existence by subtracting `n + 1` from `nums[nums[i] - 1]` (so it is `< 0`). Use a separate variable to mark the existence of `0`.

```cpp
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        bool zero = false;
        for(int num : nums){
            int val = num < 0 ? num + n + 1 : num;
            if(val == 0)
                zero = true;
            else{
                int idx = val - 1;
                nums[idx] -= (n + 1);
            }
        }
        if(!zero) return 0;
        int i;
        for(i = 0; i < n; ++i){
            if(nums[i] >= 0)
                break;
        }
        return i + 1;
    }
};
```

### Optimal solution

Idea: use XOR. Because`a XOR a XOR b == b`.

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