Assume an arithmetic progression (AP) is taken and each member is divided by powers of 2 until it becomes odd. Take such a sequence as input, and find the original arithmetic progression. (Max. 50 elements in input sequence, error checking knowingly left

AfraidOfEven.cpp

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX_32_SIGNED = 2147483647;

class AfraidOfEven
{
	vector<int> progression;
	bool findProgression(vector<int>, int);
public:
	vector <int> restoreProgression(vector <int> seq);
};

bool AfraidOfEven::findProgression(vector<int> s, int i)
{
	bool found = false;
	for (int n = s[i]; !found; n *= 2) {
		// Worst case upper limit - Find when it's started overflowing 
		// (since output is all 32-bit signed ints) and stop
		if (n < 0 || n > MAX_32_SIGNED) { 
			return false;
		}	
		if (i <= 1) {	
			s[i] = n;
		}
		else {
			int diff = s[i-1] - s[i-2];
			if (n - s[i-1] == diff) {
				s[i] = n;
			}
			else if(n - s[i - 1] > diff) {
				return false;
			}
			else {
				continue;
			}
		}
		if (i < s.size() - 1) {
			found = this->findProgression(s, i+1);
		}
		else {
			progression = s;
			found = true;
		}
	}
	
	return found;
}

vector <int> AfraidOfEven::restoreProgression(vector <int> seq)
{
	this->findProgression(seq, 0);
	return progression;
}


/* This is just testing code, not to be submitted to TopCoder */
int main(int argc, char* argv[])
{
	AfraidOfEven a;
	int arr[] = {7, 47, 5, 113, 73, 179, 53}; //One of the example inputs
	vector<int> s(arr, arr + sizeof(arr) / sizeof(arr[0]) ); // From http://stackoverflow.com/questions/2236197/c-easiest-way-to-initialize-an-stl-vector-with-hardcoded-elements/2236227#2236227

	vector<int> ans = a.restoreProgression(s);

	for (int i = 0; i < ans.size(); i++) 
	{
		cout<<ans[i]<<" ";
	}
	cin.ignore();
	return 0;
}