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 as our answer for stone game iv leetcode solution.

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

Constraints:

1 <= n <= 10

Approach:-

• Consider the dynamic programming approach for stone game iv solution.
• We make a dp array named as canWin of size n+1
• canWin[i] tells us if we have i stones then the person who starts first can win or not
• if we have 0 stones then Alice can not make a move so canWin[0]=false i.e=>alice lose
• so for i stones if there is any  j such than canWin[i-j*j]==false then canWin[i]=true  else canWin[i]=false.

Code:

Java Leetcode Solution:

class Solution {
    Boolean[]dp;
    public boolean winnerSquareGame(int n) {
        dp=new Boolean[n+1];
        return helper(n,1);
    }
    public boolean helper(int n,int b){
 
        if(dp[n]!=null)return dp[n];
        
        int i=1;
        for(;i*i<=n;i++){
         boolean  ans=  helper(n-(i*i),(b^1));
           if(!ans)return dp[n]=true;
            
        }
        return dp[n]=false;
        
    }
}

C++ Leetcode Solution:

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<bool> dp(n+1);
        for(int i=1;i<=n;i++){
            for(int j=1;j*j<=i;j++){
                if(!dp[i-(j*j)]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp.back();
    }
};

Complexity Analysis of Stone Game IV Leetcode Solution:

Time Complexity:

The Time complexity is O(nsqrt(n)).

Space Complexity:

The Space Complexity is O(n).