Searching: Find the missing number

Problem Statement:

You are given an array with distinct range of [1, n].

There is one element missing. Find the missing element in the array

Example:

Input:
a = [4, , 2, 3, 1, 5, 8, 7 ]

Output: 6

Solution 1: Brute force approach

Run 2 nested loops from 1 to n.

Then check if any of the number is missing and return the value.

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

Solution 2: Hash map 

use a hash map to store the value and store the frequency of the element.

Then iterate through the hash array to find the missing number.

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

Solution 3: Sum of n terms

Use the below formula to find the first n numbers in the list. (n * (n + 1)) / 2.

Then find the sum of the array, subtract the array with the above result to reg the solution.

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

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;

int solution_1 (vector<int>& arr) 
{

    int n = arr.size() + 1;

    for (int i = 1; i <= n; i++) 
    {

        bool found = false;
        for (int j = 0; j < n - 1; j++) 
        {
            if (arr[j] == i) 
            {
                found = true;
                break;
            }
        }

        if (!found)
            return i;
    }
    return -1;
}

int solution_2 (vector<int> &arr) 
{

    int n = arr.size() + 1;

    vector<int> hash(n + 1, 0);

    for (int i = 0; i < n - 1; i++) 
    {
        hash[arr[i]]++;
    }

    for (int i = 1; i <= n; i++) 
    {
        if (hash[i] == 0) 
        {
            return i;
        }
    }
    return -1;
}

int solution_3 (vector<int> &arr) 
{

    int n = arr.size() + 1;
  
    int sum = 0;

    for (int i = 0; i < n - 1; i++) 
    {
        sum += arr[i];
    }

    long long expSum = (n * (n + 1)) / 2;  

    return expSum - sum;
}

int main() {
    vector<int> arr = {4, 2, 3, 1, 5, 8, 7}; 

    cout << solution_1(arr) << endl; 
    cout << solution_2(arr) << endl; 
    cout << solution_3(arr) << endl;
     
    return 0;
}

Output

6
6
6