Find the missing integer – The Coding Interview Blog

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