## Solution to the ACM Programming Problem 1

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.
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. 😉 1. 