© Parineeth M R
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