Last Updated: 11 Dec, 2020
Missing number in Arithmetic progression
Easy
Asked in companies
You are given a sorted array of ‘N’ distinct integers that are in the Arithmetic Progression sequence except for one element which is missing from the sequence. You have to find that missing number from the given sequence.
Note:
1. A sequence [arr0, arr1,…, arr(n-1)] is called an Arithmetic progression if for each 'i' ( 0 ≤ i < n - 1) the value arr[i+1] − arr[i] is the same.
2. There is exactly one missing number in the given sequence.
3. All the numbers present in the sequence are distinct.
4. It is the guarantee that the first and last elements of the sequence are not missing elements.
Follow Up
The overall run time complexity should be O(log(N)).
Input Format:
The first line of the input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single positive integer ‘N’ denoting the number of the elements present in the sequence.
The second line of each test case contains ‘N’ space-separated integers.
Output Format:
The only line of output of each test case should contain an integer denoting the missing element in the given sequence.
Print the output of each test case in a separate line.
Constraints:
1 <= T <= 50
3 <= N <= 10 ^ 4
-10 ^ 9 <= Arr[i] <= 10 ^ 9
Where ‘T’ is the number of test cases, ‘N’ is the size of the array and ‘Arr[i]’ is the size of the array elements.
Time Limit: 1 sec
Approaches
- First of all, we find the first term and the common difference of the given sequence.
- As we know that the given sequence is sorted therefore, the first term of AP will be the first number present in the given sequence, i.e., arr[0].
- We know that there are ‘N’ elements in the sequence except for the one element which is missing, so the total number of elements that should be in the sequence will be N+1. Thus the last element of the sequence should be (N+1)th term of the given sequence.
- To find the common difference let's use the formula:-
1. A(N) = a + (N-1)*d, where A(N) is the Nth term, a is the first term and d is the common difference of the AP.
2. We will use the above formula to find common difference
A(N+1) = a + N*d
arr[n-1] = arr[0] + N*d
Hence, d = (arr[n-1] - arr[0]) / N
- Now we know the common difference of AP we will check if the difference between adjacent elements of the sequence has this as their difference or not. If the difference between adjacent elements is not the same as the common difference, that means the missing element will be between these two elements.
- So if we found the mismatch at index ‘i’ then the value of the missing element as per the formula will be arr[0] + i*d (0th based indexing).
- We find the first term and common difference from the same procedure as explained above.
- Now we will apply a binary search to find the position of the missing element.
- Let us take L=0, R = N-1 as our index range for binary search then we find mid as (L+R)/2, and we calculate the difference between adjacent elements present on both the sides of mid, i.e., mid+1 and mid-1.
- If the difference ( arr[mid+1] - arr[mid] ) is not the same as the common difference then we know that our missing element will lie between arr[mid] and arr[mid+1]. We will do the same check for mid and mid-1 also.
- Else if the difference is the same as the common difference, then we have to reduce our search space and shift either right or left.
- To reduce the search space, we check if the elements till mid are following the AP or not. Using the formula, we will find the (mid+1)th term ( 0th based indexing ) of the AP. Suppose this term is equal to b[mid]. It means that all elements till mid are following an AP so, in this case, we will search our missing element on the right-hand side of the mid, i.e., from ‘mid+1’ to ‘R’.
- If arr[mid] is not equal to (mid+1)th term then we know that the missing element will be on the left-hand side so, in that case, we will reduce our search space to [L,mid-1].
Similar problems