kikit
6/27/2016 - 7:31 AM

Find the missing number in Arithmetic Progression

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;
}