Question: You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer. Example: Input: [1, 2, 4, ,6, 3, 7, 8] Output: 5 Solution: There is a very simple sum formula for this solution.just have to use that formula. Formula: 1. Get the sum of numbers total = (n+1)*(n+2)/2 2 Subtract all the numbers from sum and you will get the missing number. Sample Code: /** * @author Abhinaw.Tripathi * */ public class MissingNumber { public static int getMissingNo(int arr[],int n) { int total,i; total=(n+1)*(n+2)/2; for(i=0;i<n;i++) total-=arr[i]; return total; } public static void main(String[] args) { int a[] = {1,2,4,5,6}; int miss = getMissingNo(a,5); System.out.println("Missing Number is: "+miss); } }
Result: Missing Number is: 3
Time Complexity: O(n)
Note: There can be overflow if n is large. In order to avoid Integer Overflow, we can pick one number from known numbers and subtract one number from given numbers. This way we wont have Integer Overflow ever.
Will happen if we take n such that n(n+1)/2 > INT_MAX .