I've been given the following problem in an interview (that I've already failed to solve, not trying to cheat my way past): The game starts with a positive integer number $A_0$. (E.g. $A_0 = 1234$.) This number is converted to binary representation, and $N$ is the number of bits set to $1$. (E.g. $A_0 = b100\ 1101\ 0010$, $N = 5.$)
Player 1 chooses a number $B_0$ lesser than $A_0$. $B_0$ must have only one bit set to 1. (E.g. $B_0 = b10\ 0000\ 0000 = 512$.) Let $A_1 = A_0 - B_0$. (E.g. $A_1 = 1234-512 = 722 = b10 1101 0010$.) A move is valid if $B_0$ satisfies the previous constraints, and if the number of bits set in $A_1$ is still equal to N.
Player 2 continues from $A_1$ by choosing a valid $B_1$, then player 1 continues from $A_2$, and so forth. A player loses if they have no valid moves left.
Assuming both players play optimally, determine the winning player using a reasonably efficient method. (In my problem definition, the constraints on this were that the program has to be able to deliver a solution for a few million input numbers that fit into a signed 32-bit integer.) That is, the solution doesn't need to be fully analytical.
My personal interest here is figuring out whether the expectation of me to have found and implemented the correct solution with no way feedback on correctness in the 120 minutes I was given was reasonable; or if this was one of those "let's see if they've seen this puzzle before" questions.
I'd failed because I chose to implement what seemed like a reasonable strategy, that gave me correct results for the few test cases that I've been given up front, wasted too much time making this run fast, and ended up handing in incorrect full output as my time ran out.
In retrospect I should've implemented a brute-force search and memorized partial solutions for small starting numbers, but hindsight is always 20/20. I'm curious however if there's a different common approach that eluded me as a flunkee.