Hashing: Given an array, you need to find the missing number

Coding Interview Questions

1 min read

Problem Statement:

Given an array of size n in the range [0, n, you need to find the missing number.

Example:

Input: s = [0, 3, 1]
Output: [2]

Solution Explanation:

In this approach, we will add all the numbers into the hash table.

Then check each number into the hashtable and if you get any missing number return the result else return -1.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int>& nums) 
{
    unordered_set<int> unorderedSet;  
    int n = nums.size();

    for (int num : nums) 
    { 
        unorderedSet.insert(num);
    }
    
    for (int i = 0; i <= n; ++i) 
    {
        if (!unorderedSet.count(i)) 
        {
            return i;
        }
    }
    return -1;  
}

int main() 
{
    vector<int> arr = {0, 3, 1};


    cout << solution(arr);

    return 0;
}