---
# System prepended metadata

title: 268. Missing Number
tags: [math, Leetcode, bit, python, c++, easy]

---

###### tags: `Leetcode` `easy` `math` `bit` `python` `c++`

# 268. Missing Number

## [題目連結:] https://leetcode.com/problems/missing-number/description/

## 題目:
Given an array ```nums``` containing ```n``` distinct numbers in the range ```[0, n]```, return the only number in the range that is missing from the array.

**Example 1:**
```
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
```
**Example 2:**
```
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
```
**Example 3:**
```
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
```

**Follow up**: Could you implement a solution using only **O(1)** extra space complexity and **O(n)** runtime complexity?

## 解題想法:
* 此題為給一長度n的數組，其中值0~n，求缺少的某數
* 限制: using only O(1) extra space ,O(n) runtime
* 法1:
    * 用**xor**，把nums中n格數與完整的1~n個數**xor**，即可找出剩下的那一個
    * XOR概念:
        * 0^0 = 0
        * b^b = 0
        * 0^a = a
        * b^a^a = b
* 法2:
    * 加總n數和，再逐一減去nums中的數，即可找出剩下的那一個
    * [0,1,2,4] total= 0+1+2+3+4 = 10 = (4*(4+1))/2 
        * (上底+下底)*高/2 


## Python:
``` python=
class Solution(object):
    def missingNumber(self, nums):
        #限制:
        #using only O(1) extra space ,O(n) runtime
        res=0
        n=len(nums)
        for i in range(n+1):
            res^=i
        for val in nums:
            res^=val
        return res   
        '''
        #法2 :
        n=len(nums)
        total=((n+1)*n)/2
        for val in nums:
            total-=val
        return total
        '''
    
if __name__ == '__main__':
    result = Solution()
    nums = [9,6,4,2,3,5,7,0,1]
    ans = result.missingNumber(nums)
    print(ans)
```

## C++:
``` cpp=
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res=0, n=nums.size();
        for (int i=1; i<n+1; i++) res^=i;
        for (auto val: nums) res^=val;
        return res;
    }
};
``` 