# Find the Missing Number in an Array

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

Example 1:

```Input: [3,0,1]
Output: 2
```

Example 2:

```Input: [9,6,4,2,3,5,7,0,1]
Output: 8
```

Note:
Your algorithm should run in linear run time complexity. Could you implement it using only constant extra space complexity?

## Basic Knowledge

#### Formula :

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

sum = 10 * (10 + 1) / 2;

## Steps to solve

### Step 1

• With the above formula of how to find the sum of given length, find the sum for length of an array.
• If the size of an array is 10, then sum will be 55.

### Step 2

• Find the actual sum of the array. i.e if array has {3,0,1} then actual sum will be 4;

### Step 3

• Consider array has {3, 0, 1}, the actual sum will be 4.
• The length of an array, here is 2.
• Calculate the sum for length 2, that is 2 * (2+1)/2 = 2;
• Find the difference of sum and actual sum, that’s the answer.
• sum – actual sum = 4 – 2 = 2.
• So, 2 is the missing number, we got the answer here.

## Solution

### Java Program

```class Solution {
public int missingNumber(int[] nums) {

//Finding total sum of an array
int sum = nums.length * (nums.length+1)/2;

int actualSum = 0;
//Calculate the actual sum
for(int n : nums)
{
actualSum += n;
}

//missing number
return sum-actualSum;
}
}```