Find Missing Number In An Array In One Iteration

Companies:
  • Amazon Interview Questions
  • Apple Interview Questions
  • Microsoft Interview Questions

Given an array containing n distinct numbers taken from 1, 2, ..., n + 1, find the one that is missing from the array.

Example 1:

Input: [1,2,4]

Output: 3

Example 2:

Input: [5,3,7,4,2,1]

Output: 6

Solution

This problem can be solved in many ways, but to ensure it’s efficiency, here’s the most easy and efficient solution:

Algorithm:

You have already heard about Gauss Formula of summation of first n natural numbers.

Gauss Formula = n*(n+1)/2.

With this we only have to calculate the summation of natural numbers as n will be equal to the length if the given array!

Then iterate the whole array and find it’s sum, and the difference between expected and calculated sum will give you the required missing number.

Solution Implementation

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

int main() {
    vector<int> vec = { 1, 3, 2, 5 };
    
    int n = vec.size() + 1;
    
    // From Gauss formula
    int expectedSum = (n*(n + 1))/2;
    
    int actualSum = 0;
    for(int i = 0; i < vec.size(); i++) {
        actualSum += vec[i];
    }
    
    cout << "Missing number is " << expectedSum - actualSum << "\n";
    
    return (0);
}

 

Complexity Analysis:

  • Time Complexity: O(n).
  • Space Complexity: O(1).
Scroll to Top