268. Missing Number

• Difficulty: Easy

• Topics: Array, Math, Bit Manipulation

• Similar Questions:

  • First Missing Positive

  • Single Number

  • Find the Duplicate Number

  • Couples Holding Hands

Problem:

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?

Solutions:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            kick(nums, i);
        }

        for (int i = 0; i < n; ++i) {
            if (nums[i] != i) {
                return i;
            }
        }

        return n;
    }

    void kick(vector<int>& nums, int i) {
        int val = nums[i];
        nums[i] = -1;

        while (val < nums.size() && val >= 0) {
            swap(val, nums[val]);
        }
    }
};