Stone Game IV

Explanation of Problem Statement

In this problem, Alice is the starting player who starts the game first. In each step, the player has to make a move of square number; if the move can not be possible, the person loses the game. If “Alice” wins, return true otherwise false.

Let’s take some examples to understand the problem:

1. If the value of N=4 or any perfect square, Alice is the winner because he will start the game, and the answer is always “true”
2. If the value of N=7. Then we choose to move with a perfect square, which optimally requires that Alice be the winner.

Now for that, we have 1, 4 are only two perfect squares.

1. If Alice chooses 1 then we have 6 remaining for which we have 1 and 4 two choices then if we go we 1 next so on then we find Bob played the last one same with the choosing 4 and making the cases of the perfect square we find Bob as winning here also.
2. If Alice chooses 4, then 3 we have for that 1 is an only perfect square, then Bob plays, remain is 2 then Alice plays, then 1 remain then Bob will play, and 1 is itself as a perfect square, then for the next chance of, no stone remaining thus Bob wins the race.
3. The answer is “False.”

 

The main point here is a perfect square, which is the deciding factor. Hence, we have to find the ways for all the ideal squares present <=N for which Alice should be the winner. If that case is not going to be possible in every possible case, then Bob is an inner we simply return “False” if in any case “Alice” made it we return “True.”

Solution

Here we are going to solve the problem using two approaches one is recursive as we are performing the same task repeated, and one is Dynamic Programming approaches because of some repeated task is going to solve multiple times, because that, we store the answer in dp array, which directly helps to find the solution.

Two Approaches are:-

1. Recursive Approach
2. Dynamic Approach
3. Top-Down 
4. Bottom-Up

 

Recursive Solution

In this approach, we consider all the possible perfect squares <= N to find the possible way. Is there any way Alice wins the game if no possible way is found? Simply return the answer as Bob will succeed and return False.

 

Let’s Take an example of it.

Eg : N=7 

OUTPUT: FALSE

7

Possible perfect squares less than or equal to 7 are 1 and 4 only.

Here below PS -> Perfect Square <=N.

 

 

Both players play optimally, and thus, Bob is the last player, and nothing is left for Alice’s turn, so Bob wins the game, and the answer is “False.” 

 

Algorithm for the Recursive Solution:

1. Take an input “N” from the user, which denotes no stone in piles.
2. Create a function, which is going to find the solution for us.
3. Winnergame_rec function checks for all possible cases of perfect square <=N.
4. We declare the one boolean variable which keeps track of the winning player.
5. Base condition to Terminate when we have no stone left.

Code for the Recursive Solution:

 

import java.util.Scanner; public class SG_IV {   /*Recursive Solution*/   static boolean winnergame_rec(int n){       if(n==0) return false;       boolean winner=false;       for(int i=1;i*i<=n;i++){           if(!winnergame_rec(n-i*i)){               winner=true;               break;           }       }       return winner;   }   public  static void main(String [] args){       Scanner sc=new Scanner(System.in);       int n=sc.nextInt();       boolean flag=winnergame_rec(n);       if(flag==true){           System.out.println("true");       }       else {           System.out.println("false");       }   } }

 

Input:

 

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

 

Time Complexity: Time complexity is O(N*sqrt(N)) with some solved subproblem is solved again and again.

 

Space complexity: O(1), as no extra space is required.

Top-Down Solution(DP)

As seen in the above Recursive approach, we have some repeated sub-task. To avoid repeated calculation of the same problem, we use a dp array to store the solution.

Algorithm for Top-Down Solution:

1. We create a dp array to store the solution to solve sub tasks.
2. If we encounter no null value in DP Array, we directly return the value for the problem, as it was previously? solved and stored.
3. Now we run a loop to solve the problem if a new sub-task is encountered, then after the completion of the loop, the value of the winner is assigned in the dp Array and returned.

Code for Top-Down Solution:

 

import java.util.Scanner; public class SG_IV {   /*Top-Down Approach*/   static Boolean [] dp=new Boolean[100001];   static boolean winnergame_td(int n){       if(n==0) return  false;       if(dp[n]!=null) return dp[n];       boolean winner=false;       for(int i=1;i*i<=n;i++){           if(!winnergame_td(n-i*i)){               winner=true;               break;           }       }       return dp[n]=winner;   }   public  static void main(String [] args){       Scanner sc=new Scanner(System.in);       int n=sc.nextInt();       boolean flag=winnergame_td(n);       if(flag==true){           System.out.println("true");       }       else {           System.out.println("false");       }   } }

 

Input:

 

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

 

Time Complexity: Time Complexity of the problem is O(N*sqrt(N))

 

Space Complexity: using extra space of O(N) to stop further calculation of repeated sub-task.

As already the problem solved is stored in the dp Array if we encounter dp[n]!=null then return dp[n] directly.

 

Bottom-Up Solution(DP)

In the bottom-Up Approach, we create a dp Array of size N+1 and start filling the array by running the stone number 1 to N, with possible optimal solutions for a particular i value by finding a solution for all the perfect squares <=i. 

Algorithm for Bottom-Up Solution:

1. Create an extra dp array of boolean type of size N+1.
2.  Start filling the array of every perfect square <=i with an optimal solution.
3. Choose i value to start from 1 to N and fill it with j*j<=i constraint, if any; assign the value for a particular Dp position as true.
4.  At last, a; assign, and return dp[n], which shows the previous player is the winner or loser. If it returns true, then Alice is the winner. Otherwise, Bob is a winner. 

Code for Bottom-Up Solution:

 

import java.util.Scanner; public class SG_IV {   /*Bottom-Up Approach*/   static boolean winnergame_bu(int n){       boolean [] dp=new boolean[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[n];   }   public  static void main(String [] args){       Scanner sc=new Scanner(System.in);       int n=sc.nextInt();       boolean flag=winnergame_bu(n);       if(flag==true){           System.out.println("true");       }       else {           System.out.println("false");       }   } }

 

Input:

 

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

 

Time Complexity:  By running an internal loop of O(sqrt(N)) and outer is O(N) so with Time Complexity of O(N*sqrt(N).

 

Space complexity: Space Complexity is O(N+1) ~ O(N), to fill the Dp Array.

Frequently Asked Question

1). How can someone realize that the same problem can also be approached using a dynamic programming technique?

Ans: Recursive solution with some repetition is the general idea behind it most of the Time.

2). What is the Time Complexity and Space Complexity of Solution?

Ans: Time Complexity is O(N* sqrt(N)), and Space Complexity is O(N).

Key Take-Away

In this, we solve one of the problems of Leetcode, using Recursive, Top-Down, Bottom-Up Approach by following these three steps, one can get an idea of how we can think when any DP program, we have to not directly jump into the DP solution, first go with the Recursive Approach then life gets better with the use of the DP approach.

 

In this blog, we solve the problem of Stone game IV, headed up to the next scenario, where “N” stone is given in which we solve optimally and make a different branch of play based on a number of square numbers less than or equal to N, wherein previous Stone game III, the scenario is of accumulating the maximum score for collecting the stone where the score is given on stone. Here the series of Stone Game problems continues with two players who want to win the game and play optimally. By seeing these two sean of problems the optimal solution is their high chance for using the DP for optimized algorithm for the problem.

Check out this problem - Optimal Strategy For A Game

Happy Learning.