Problem of the day
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.
The overall run time complexity should be O(log(N)).
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.
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.
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
2
3
1 4 10
4
5 10 20 25
7
15
Test case 1:
The arithmetic sequence present in the first test case will have its first term as 4 and common difference as 3. So, the complete sequence will look like this ....- 1 4 7 10... Hence 7 is the missing element in the given sequence.
Test case 2:
The first term and common difference will be 5. The complete sequence will be ...5 10 15 20 25.... Hence 15 is the missing element from the given sequence.
3
3
-1 0 2
5
10 20 30 50 60
4
12 18 21 24
1
40
15