You are given an array of positive numbers from $1$ to $n$, such that all numbers from $1$ to $n$ are present except one number, $x$. You have to find $x$. The input array is not sorted.

For example, let’s look at the below array.

- How would you calculate the sum of numbers from $1$ to $n$?

#include <iostream>#include <vector>using namespace std;int FindMissing(const vector<int>& input) {//TODO: Write - Your - Codereturn -1;}

#include <iostream>#include <vector>#include <string>#include <numeric>using namespace std;int FindMissing(const vector<int>& input) {// Calculate sum of all elements in the input vector// The accumulate function can this for usint actual_sum = accumulate(input.begin(), input.end(), 0);int n = input.size();// Find the sum of first n numbers using the arithmetic series sum formula,// i.e., (n∗(n+1))/2int sum_of_n = (n * (n + 1)) / 2;// The difference between sum_of_n and actual_sum, is the missing number in the// arrayreturn sum_of_n - actual_sum;}int main() {vector<vector<int> > vec_list = {{0}, {3, 7, 1, 2, 0, 4, 5}, {9, 6, 4, 2, 3, 5, 7, 0, 1}};for (int i = 0; i < vec_list.size(); i++) {cout << i + 1 << ". Original ";// A custom function to print the vectorPrintList(vec_list[i]);int missing = FindMissing(vec_list[i]);cout << " The missing number is: " << missing << endl;cout << "\n------------------------------------------------------------------------------------------------------\n" << endl;}}

Linear, $O(n)$.

Constant, $O(1)$.

A naive solution is to simply search for every integer between 1 and n in the input array, stopping the search as soon as there is a missing number. Since the input array is not sorted, its time complexity will be $O(n^{2}$).

Can you do better than $O(n^{2}$)? Yes.

You could sort the array and then do a linear scan $O(n$) where you compare all consecutive elements to find the missing number. However, the time complexity of this algorithm is $O(n log n$) due to the time spent in sorting.

You can do better. Here is a linear, $O(n$), solution that uses the arithmetic series sum formula.

$\sum_{1}^n = \frac{n (n + 1)}{2}$

Here are the steps to find the missing number.

- Find the sum of elements of all the numbers in the array. Let’s call it
`sum`

. This would require a linear scan, $O(n)$. - Then find the expected sum of the first $n$ numbers using the formula: $\frac{(n(n+ 1))}{2}$. Let’s call it
`total`

. - The difference between
`total`

and`sum`

is the missing number in the array.

Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!

TRENDING TOPICS