# Could this be an NP-Complete problem?

Consider the following problem statement:

Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins. For example:

Initial State: 37

Player1 subtracts 16. State: 21

Player2 subtracts 8. State: 13

Player1 subtracts 4. State: 9

Player2 subtracts 9. State: 0

Player2 wins!

Write a program that given an initial state, returns an optimal move, i.e. one that is guaranteed to lead to winning the game. If no possible move can lead you to a winning state, return -1.

This problem can be solved in pseudo-polynomial time using dynamic programming. The idea is just filling an array of length n (where n is the initial state) bottom up with the optimal moves, or -1 if no move leads to winning. This would take O(n * sqrt(n)) since for every number we need to consider subtracting each possible perfect square smaller than it (there are ~sqrt(n) of them). However, this is a pseudo-polynomial runtime complexity since the runtime actually scales exponentially with relation to the size of the input in binary (# of bits used to represent number).

Can anyone think of a polynomial algorithm for solving this problem? If not, could it be NP-Complete? Why?

• Out of curiosity, why are you specifically asking if it's NP-complete? (Personally, I would have guessed that it's not even in NP, though I really don't know.) – ruakh Feb 20 '17 at 8:42
• @ruakh I recently encountered this problem during a coding interview and proposed the pseudo-polynomial solution using dynamic programming that I described. However, after carefully thinking about the problem I could not come up with a polynomial time algorithm. I soon started questioning myself if this was not in fact an NP(-Complete) problem. – Martin Copes Feb 20 '17 at 17:41
• Have you tried calculating which positions are winning positions and which are losing positions? Perhaps a pattern will arise. – Yuval Filmus Feb 20 '17 at 19:52
• @YuvalFilmus According to Wikipedia there is no known formula for this pattern (sequence A030193 in the OEIS) – Martin Copes Feb 20 '17 at 20:01
• Right, I was just going to post an answer with this information. See also A224839. – Yuval Filmus Feb 20 '17 at 20:02