Prashant | Wed, 03 Jun, 2020 | 773

One of the most frequently asked question on programming interviews is, write a program to find the missing number in an array in Java, C# or any other language; depending upon which language you choose.

This kind of coding interview questions are not only asked in small start-ups but also on some of the biggest technical companies like Google, Amazon, Facebook, Microsoft, mostly when they visit the campus of reputed universities to hire graduates.

Simplest version of this question is to* find missing elements in an area of 100 integers*, which contains numbers between 1 and 100. This can easily be solved by calculating the sum of the series using n(n+1)/2, and this is also one of the quickest and efficient ways, but it cannot be used if the array contains more than one missing numbers or if the array contains duplicate numbers.

This gives interviewer some nice follow-up questions to check whether a candidate can apply his knowledge of the slightly different condition or not. So if you get through this, they will ask you to find the missing number in an array of duplicates. This might be tricky but you will soon find out that another way to find missing and duplicate number in the array is to sort it.

In a sorted array, you can compare whether a number is equal to expected next number or not. Alternatively, you can also use BitSet in Java to solve this problem.

**To try in Code part **

In CPP language

```
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum=0;
for(int i=0;i<nums.size();i++) sum+=nums[i];
int sum2=(nums.size()*(nums.size()+1))/2;
return sum2-sum;
}
};
```

```
class Solution {
public int missingNumber(int[] nums) {
int ans = nums.length*(nums.length+1)/2,sum=0;
for(int i = 0 ; i < nums.length ; i++)
sum+=nums[i];
return ans-sum;
}
}
```

Let A = {1, 2, 3, 4, ..., n}

sum(A) = n * (n + 1) / 2

Why so:

sum(A) = 1 + 2 + 3 + 4 + ... + n

sum(A) = n + (n - 1) + (n - 2) + ... + 1

2sum(A) = (n + 1) * n => sum(A) = (n + 1) * n / 2

(The method was founded by kid Gauss)

nums = {x | x >= 0 && x <= n} - {missed num | missednum >= 0 && missednum <= n}

this means missed num: n * (n + 1) / 2 - sum(nums)