So the other day month, I posted a programming problem from the ACM inter-collegiate programming competition that I did last year. Here’s my plain-English solution (with some code too). And yes. It is three months late.

Well, there were a large number of people who solved the problem in virtually no time (including a solution in Factor, which I’d never heard of), showing me just how bad I am at these things. Not only that, but they solved it using methods and shortcuts I’d never even dreamed of. My solution was a simple bruteforce, and it goes a little something like this:

“UpperBound(n)” here means every number (up to an including n) added together. q is the answer of the sum, that is, the input.

1. Get q.
2. Start n=1. Discard as UpperBound(n)<q.
3. n=2. Discard as UpperBound(n)<q.
4. n=3,4, discard as UpperBound(n)<q.
5. n=5, discard as UpperBound(n) and q are not both divisible by 2.
6. n=6, discard as UpperBound(n) and q are not both divisible by 2.
7. n=7, UpperBound(n) and q are both divisible by 2, an answer exists. Print n, end.

Didn’t make sense to you? That’s okay! I copied that verbatim from my whiteboard. Here’s some (C/C++) code, instead.

#include <iostream>

int getUpperBound(int n){
	int upperBound = 0;
	while (n > 0){
		upperBound += n;
		n--;
	}
	return upperBound;
}

bool getN(int q, int n){
	if (getUpperBound(n) < q) {
		return false;
	} else {
			//check for divisibility (if q/2 then upperbound of n _must_ also be /2
		if (((getUpperBound(n)%2==0) && (q%2==0)) || (!(getUpperBound(n)%2==0) && !(q%2==0))) {
			return true;
		} else {
			return false;
		}
	}
}

	//get q elsewhere, like a text file
int main (int q) {
	q = 12;

	if (q < 0){
			//should use absolute value here instead, not that it makes a difference
		q+=(0-q)*2;
	}

	int i = 1;
	while((getN(q, ++i)) != true); //prefix used so there's no off-by-one error
	std::cout << i << std::endl;
}

That code ought to compile in the majority of popular C/C++ compilers – I wrote it in XCode and compiled with GCC. However, the input doesn’t conform to the competition’s typical text-file input standards – in fact, there is no input. To check the algorithm with another number, just change q in the main method.

My apologies for the three months of delaying – although I’m sure nobody waited that long for the (probably inefficient, insufficiently-explained) answer. 😉