###### 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:

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++:

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;
    }
};