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?

  • 1
    $\begingroup$ 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.) $\endgroup$
    – ruakh
    Feb 20 '17 at 8:42
  • $\begingroup$ @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. $\endgroup$ Feb 20 '17 at 17:41
  • $\begingroup$ Have you tried calculating which positions are winning positions and which are losing positions? Perhaps a pattern will arise. $\endgroup$ Feb 20 '17 at 19:52
  • $\begingroup$ @YuvalFilmus According to Wikipedia there is no known formula for this pattern (sequence A030193 in the OEIS) $\endgroup$ Feb 20 '17 at 20:01
  • $\begingroup$ Right, I was just going to post an answer with this information. See also A224839. $\endgroup$ Feb 20 '17 at 20:02

The sequence of losing positions can be found in the OEIS, A030193, as is the sequence of positions having Grundy value 1, A224839. The encyclopedia cites several relevant articles. Perhaps some of them discuss non-trivial algorithms for computing the sequence.

  • $\begingroup$ As you mentioned, this sequence represents the losing positions. Even if you were able to check in constant time whether a position loses or not (which seems hard!) the problem still asks you to return the optimal move, i.e. what square you would need to subtract to the current state in order to get to a losing position. The problem would boil down to finding a losing position by subtracting squares from the current state. So you still need to iterate through all the squares smaller than the state, even if you could check if a position is losing in constant time. $\endgroup$ Feb 20 '17 at 20:30
  • 3
    $\begingroup$ Right, it won't be enough, but it will be a good start. Perhaps you'll gain some insight from being able to calculate just the winning status of a position. Plus, showing that it is hard to decide which position is losing will be enough to show that your problem as stated is NP-hard, in any reasonable decision version. $\endgroup$ Feb 20 '17 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.