C++ Coding Exercise – How to Find First Missing Number?

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

How many solutions can you think of? Submit your solution at: https://leetcode.com/problems/missing-number/

Using Set

Set data structure is usually not constant complexity. It should be at least O(logn) depending on algorithms. However, using Set is a practical solution and is quick to implement.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int len = nums.size();
        unordered_set<int> cache;
        for (int i = 0; i < len; i ++) { 
            cache.insert(nums[i]); // put in the hash set
        }
        for (int i = 0; < <= len; i ++) {
            if (!cache.count(i)) { // not in the set list
                return i;
            }
        }
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int len = nums.size();
        unordered_set<int> cache;
        for (int i = 0; i < len; i ++) { 
            cache.insert(nums[i]); // put in the hash set
        }
        for (int i = 0; < <= len; i ++) {
            if (!cache.count(i)) { // not in the set list
                return i;
            }
        }
    }
};

Time Complexity O(n). Runtime 100ms

Using XOR

We must remember the fact that any number XOR itself twice becomes zero. So if we XOR all numbers from 0 to n twice that becomes zero as well. Since there is only 1 missing number, the XOR result will be equal to that number.

1
2
3
4
5
6
7
8
9
10
11

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

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

This is the most efficient solution because the space complexity is just O(1) (excluding the given inputs). This runs at 36ms.

Sum

Similarly, we know the sum from 0 to n, so we can subtract the sum with the sum of given inputs, the difference will be the missing number.

1
2
3
4
5
6
7
8
9
10

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

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

This gets accepted at 34ms, however, the sum may overflow the integer types.

Could you come up with different ideas? comment below.

–EOF (The Ultimate Computing & Technology Blog) —