 # Find Missing Number In An Array In One Iteration

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

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

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.