Find the missing number in Arithmetic Progression
/*
http://ideone.com/fDIHl5
http://www.geeksforgeeks.org/find-missing-number-arithmetic-progression/
http://www.practice.geeksforgeeks.org/problem-page.php?pid=896
*/
#include <iostream>
#include <string>
#include <limits.h>
using namespace std;
int findMissing(int a[], int left, int right, int diff){
if(right <= left)
return INT_MAX;
int mid = left + (right - left) / 2;
if(a[mid+1] - a[mid] != diff)
return (a[mid] + diff);
if(mid > 0 && (a[mid] - a[mid-1]) != diff)
return (a[mid] - diff);
if(a[mid] == a[0] + mid*diff)
return findMissing(a, mid+1, right, diff);
return findMissing(a, left, mid-1, diff);
}
int main() {
int t, n;
cin >> t;
while(t--){
cin >> n;
int a[11];
for(int i=0; i<n; i++)
cin >> a[i];
int diff = (a[n-1] - a[0]) / n;
cout << findMissing(a, 0, n-1, diff) << endl;
}
return 0;
}