# Stone Game IV LeetCode Solution

Difficulty Level Hard
Dynamic Programming MathViews 920

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

Translate »