# Find the missing integer

Question 49. An unsorted array contains all integers from 1 to N except one integer. All the elements in the array are unique. Find the missing integer in O(n) time and O(1) space. For instance in the array {5, 1, 3, 2}, the missing element is 4

All integers from 1 to N are present in the array except one integer. To find the missing integer we do the following

1. Calculate the expected_sum of integers from 1 to N. We know that the sum of integers from 1 to N is given by the formula N * (N+1) / 2

2. Calculate the total_sum of the N-1 elements in the array.

3. The difference between expected_sum and the total_sum will give the missing element.

So if N = 5, and array is {5, 1, 3, 2}, then expected sum = 5 (5 + 1) / 2 = 15. The total sum of elements in the array = 5 + 1 + 3 + 2 = 11. So missing number = 15 – 11 = 4.

## C/C++

```
/*
a: array of unique numbers. A number can have a value between 1 to n.
n: maximum value that can be stored in array. array has n-1 elements
Return value: missing element in the array
*/
int find_missing(int a[], int n)
{
int i, total_sum, expected_sum;
int missing_num;

/*Since 1 element is missing, there are only n-1 elements in the array*/
total_sum = 0;
for (i = 0; i < n - 1; ++i) {
total_sum += a[i];
}

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

missing_num = expected_sum - total_sum;

return missing_num;
}

```

## Java

```
/*
a: array of unique numbers. A number can have a value between 1 to n.
n: maximum value that can be stored in array. array has n-1 elements
Return value: missing element in the array
*/
public static int findMissing(int[] a, int n) {
/*Since 1 element is missing, there are only n-1 elements in the array*/
int totalSum = 0;
for (int i = 0; i < n - 1; ++i) {
totalSum += a[i];
}

int expectedSum = n * (n+1) / 2;

int missingNum = expectedSum - totalSum;

return missingNum;
}

```

## Python

```
#a: list of unique numbers. A number can have a value between 1 to n
#n: maximum value that can be stored in the list. list has n-1 elements
#Return value: missing element in the list
def find_missing(a, n) :
#Since 1 element is missing, there are only n-1 elements in the list
total_sum = 0
for  i in range(0, n - 1):
total_sum += a[i]

expected_sum = n * (n+1) // 2

missing_num = expected_sum - total_sum
return missing_num

```