Stone Game IV

Stone Game IV

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

• 1 <= n <= 10^5

Solutions

🧠 Cpp

class Solution
{

    std::map<int, bool> cache; 
public:
    //DP solution
    //very simullar to "Climbing Stairs"
    bool winnerSquareGame(int n)
    {
        //DP cache check
        auto found = cache.find(n);
        if(found != end(cache))
            return found->second;

        //if square
        double n_sqrt = sqrt(double(n));
        if( n_sqrt - int(n_sqrt) == 0 )
            cache[n] = true;
        //iterate over all squares that we can take (all variants)
        //if there at leaest one variant where we win, we win
        else
        {
            bool i_won = false;
            vector<int> stones_to_take;
            for(int i = 1; i*i < n; ++i)
                stones_to_take.push_back(i*i);

            //start with the bigest number of stones we can take
            //and iterate down
            for(auto stone_num = rbegin(stones_to_take);
                stone_num < rend(stones_to_take);
                ++stone_num)
            {
                //check if next player lose if we take i*i stones
                if(!winnerSquareGame(n - *stone_num))
                {
                    i_won = true;
                    break;
                }
            }
            cache[n] = i_won;
        }

        return cache[n];

    }
};