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

# Missing Number

https\://leetcode.com/problems/missing-number/description/

> Given an array containingndistinct numbers taken from`0, 1, 2, ..., n`, find the one that is missing from the array.
>
> For example,\
> Givennums=`[0, 1, 3]`return`2`.
>
> **Note**:\
> Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

## Thoughts

由0\~n构成的数组少了一个数，让找出丢失的数。这题有多种解法. 可以把应当的sum是多少用高斯法算出来, 再加出来现有sum是多少, 两个一减即Missing的.

## Code

```java
class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int tsum = 0;
        for (int i = 0; i <= nums.length; i++) {
            tsum += i;
        }

        return tsum - sum;
    }
}
```

## Ver.2

利用xor相同数会消掉的原理, 让nums和0\~n xor一下, 剩下的即所求.

```cpp
/*
 * @lc app=leetcode id=268 lang=cpp
 *
 * [268] Missing Number
 *
 * https://leetcode.com/problems/missing-number/description/
 *
 * algorithms
 * Easy (49.10%)
 * Likes:    1073
 * Dislikes: 1465
 * Total Accepted:    311.6K
 * Total Submissions: 634.1K
 * Testcase Example:  '[3,0,1]'
 *
 * 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?
 */
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        const int N = nums.size();
        int res = 0;
        for (int i = 0; i < N; ++i) {
            res ^= i;
            res ^= nums[i];
        } 
        res ^= N;
        return res;
    }
};


```

## Analysis

时间复杂度O(N), 空间O(1).