Missing Number

Problem

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.

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

Constraints

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Solution

The problem Missing Number can be solved by subtracting the sum of numbers in the array from the sum of numbers in the range [0, n] as there is only 1 number that is missing.

Implementation

class Solution
{
  public:
    int missingNumber(vector<int> &nums)
    {
        int size = nums.size();
        int sum = size * (size + 1) / 2;

        for (int i = 0; i < size; i++)
            sum -= nums[i];

        return sum;
    }
};