Solution to the TopCoder SRM 439 Div 1 250-point problem

After much head-scratching, misinterpreting the problem statement, and trying to code a solution, I gave in and looked at the #1 coder's code. I was surprised to see not more than seven elegant and fast lines of code that were able to solve the problem.

blueblimp's (and many others') solution:

struct PouringWater {
  int getMinBottles(int N, int K) {
    for (int X=0; ; X++)
      if (__builtin_popcount(N+X) <= K)
        return X;
    }
  }
}

(__builtin_popcount(unsigned int) is a gcc built-in that returns the number of 1-bits in an unsigned int.) Being able to reduce the given problem description to a solution approximating the above is an indicator of great coding talent, hats down. With the NSA sponsoring this match, I knew that something was up with the problem statement. From the above code I came up with an alternative problem description:

Let N be a number between 1 and 10,000,000 and K be the maximum number of factors. What is the closest number to N (including N itself, but not smaller than N) that has at most K unique binary factors (multiples of 2)?

Those rogues at the NSA... ;-)