Stone Game IV LeetCode Solution

Difficulty Level Hard

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