# 268. Missing Number

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?

# Solution

Approach 1: Sorting.

Approach 2: Hash table.

Approach 3: Bit manipulation.

Approach 4: Math.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] != i)
               return i;
        }
        return nums.size();
    }
};

Approach 2:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> allNums;
        for (int i = 0; i < nums.size(); ++i)
        {
            allNums.insert(nums[i]);
        }
        for (int i = 0; i <= nums.size(); ++i)
        {
            if (allNums.find(i) == allNums.end())
               return i;
        }
        return -1;
    }
};

Approach 3:

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

Approach 4:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = nums.size() * (nums.size() + 1) / 2; // Gauss's Formula.
        for (int i = 0; i < nums.size(); ++i)
        {
            sum -= nums[i];
        }
        return sum;
    }
};

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