Given a list of unsorted numbers 1…n , we need to find the missing element assuming that if we sort the array, we will get consecutive number except one missing number. Note that the list always have 1 as a member.
Example: 1,3,5,4,6,8,9,2 Ans = 7 Since if we sort the array we get 1,2,3,4,5,6,8,9 and we can see 7 is missing
Solution:
We can sort the list in O(NlogN) time and iterate through the array and check if A[i] ≠ A[i+1]. If so we find the missing one. But we can do better than O(NlogN) here by using a simple formula.
To solve this problem in linear time we have to use a math formula to get the sum of consecutive numbers.
1+2+3+4….N = n (n+1) / 2 where n is the size of the array.
Example: 1+2+3+4+5 = 5(6)/2 = 15
Therefore to find the missing number first we will find the sum with the above formula and the sum of the given array and we will subtract each other to find the answer.
Note: When we calculate N, we need to consider the missing element so we add one to it (N+1)
int N = A.Length + 1;
int calctotal = N * (N + 1) / 2;
int actualtotal = 0;
foreach (int i in A) {
actualtotal += i;
}
return calctotal - actualtotal;