# 268 - Missing Number

解法一 - Cyclic Sort

跟 cyclic sort 一樣，我們可以把各個 element 放到對的位置。唯一一點不同的地方是，剛好會有一個 element 是超過 array index 範圍，遇到這個 element 的話，我們可以跳過，反正只要把剩下的 n-1 個都放到對的位置（0 ~ n 總共有 n + 1 個 element，扣掉 missing 的還有 n 個，再扣掉超過範圍的那個，剩 n - 1 個），最後超過的那個 element 就會被放在 missing 的那一個 index。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n){
            int j = nums[i];

            if(j < n and nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else{
                ++i;
            }
        }

        // Find the first wrong number
        int missed = n; // Init missed = n, maybe we have case like this: [0]
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i) {
                missed = i;
                break;
            }
        }

        return missed;
    }
};

解法二 - 公式解

既然我們已經知道總共數字範圍是 0 ~ n，那乾脆就先加總 array，然後再跟加總到 n 的值相減就可以得到 missing number，實作如下：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int nSum = n*(n+1)/2;
        return nSum - sum;
    }
};