# 【LeetCode】 268. 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.

> 給予一個陣列 `nums` 它包含 `n` 個不同的數字且都落在 `[0, n]` 之中，回傳範圍內唯一一個不在陣列中的數字。

## Example:

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.

## Solution

* 題目的 Follow up 中有提到，是否能提出一個答案使用 `O(1)` 的額外空間複雜度和 `O(n)` 的時間複雜度。
* 既然時間複雜度在 `O(n)`，答案就必定不需要排序。
* 我的想法是利用 `A XOR A = 0` 這點，把 0 ~ n 都 XOR 起來之後，再與陣列中每個數 XOR。
* 同樣的數字互相 XOR 都會不見，留下的數字即為答案。

### Code

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

###### tags: `LeetCode` `C++`