Stone Game IV LeetCode Solution

Problem Statement:

Stone Game IV LeetCode Solution : 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.

Examples:

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).

Approach:

Idea:

We will be solving the problem with the concept of dynamic programming. First, we can generate the recursive solution and then can optimize it using memorization.

The idea is to iterate over all possible movements and check whether we can reach a False state or not. If we can, then it means we have found a must-win strategy, else we must lose since the opponent has found a must-win strategy.

Code:

Stone Game IV C++ Solution:

class Solution {
public:
    int dp[100005];
    bool helper(int n){
        if(n==1)
            return true;
        if(n==2)
            return false;
        
        if(dp[n] != -1)
            return dp[n];
        
        bool alice = false;
        for(int i=1;i<=sqrt(n);i++){
            bool bob = helper(n-i*i);
            if(not bob){
                alice = true;
                break;
            }
        }
        return dp[n] = alice;
    }
    bool winnerSquareGame(int n) {
        memset(dp,-1,sizeof(dp));
        return helper(n);
    }
};

Stone Game IV Python Solution:

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        dp = [False]*(n+1)
        for i in range(1, n+1):
            for k in range(1, int(i**0.5)+1):
                if dp[i-k*k] == False:
                    dp[i] = True
                    break
        return dp[n]

Complexity Analysis of Stone Game IV LeetCode Solution:

• Time Complexity: The time complexity of the above code is O(n√n).
• Space Complexity: The space complexity of the above code is O(n).