Optimal Strategy for the Divisor game using Dynamic Programming
Last Updated : 10 Mar, 2023
Given an integer N and two players, A and B are playing a game. On each player’s turn, that player makes a move by subtracting a divisor of current N (which is less than N) from current N, thus forming a new N for the next turn. The player who does not have any divisor left to subtract loses the game. The task is to tell which player wins the game if player A takes the first turn, assuming both players play optimally.
Examples:
Input : N = 2
Output : Player A wins
Explanation :
Player A chooses 1, and B has no more moves.
Input : N = 3
Output : Player B wins
Explanation :
Player A chooses 1, player B chooses 1, and A has no more moves.
Approach :
This problem mentioned above can be solved using Dynamic Programming.
We will take a DP having 2 states i.e.
N -> current number left
A -> boolean value to decide if it's player A's turn or not
At each state, we will try to find all the divisors of N and will try to find the next state where the current player is winning. For player A, we will try to find the next state where the return value is true while for player B, we will try to find the next state where the return value is false (as false represents the loss of player A).
The base cases will be for N=1 where always the player A will lose and N=2 where always the player B will lose.- To find the answer, we just need to find the value of DP[ N ][ 1 ].
Below is the implementation of the above approach:
C++ // C++ program for implementation of // Optimal Strategy for the Divisor // Game using Dynamic Programming #include <bits/stdc++.h> using namespace std; // Recursive function to find the winner bool divisorGame(int N, bool A, int dp[][2]) { // check if N=1 or N=3 then player B wins if (N == 1 or N == 3) return false; // check if N=2 then player A wins if (N == 2) return true; // check if current state already visited // then return the previously obtained ans if (dp[N][A] != -1) return dp[N][A]; // check if currently it is player A's turn // then initialise the ans to 0 int ans = (A == 1) ? 0 : 1; // Traversing across all the divisors of N // which are less than N for (int i = 1; i * i <= N; i++) { // check if current value of // i is a divisor of N if (N % i == 0) { // check if it is player A's turn // then we need at least one true if (A) ans |= divisorGame(N - i, 0, dp); // Else if it is player B's turn // then we need at least one false else ans &= divisorGame(N - i, 1, dp); } } // Return the current ans return dp[N][A] = ans; } // Driver code int main() { // initialise N int N = 3; int dp[N + 1][2]; memset(dp, -1, sizeof(dp)); if (divisorGame(N, 1, dp) == true) cout << "Player A wins"; else cout << "Player B wins"; return 0; } // Java program for implementation of // optimal strategy for the divisor // game using dynamic programming import java.util.*; class GFG { // Recursive function to find the winner static int divisorGame(int N, int A, int dp[][]) { // Check if N = 1 or N = 3 then player B wins if (N == 1 || N == 3) return 0; // Check if N = 2 then player A wins if (N == 2) return 1; // Check if current state already visited // then return the previously obtained ans if (dp[N][A] != -1) return dp[N][A]; // Check if currently it is player A's turn // then initialise the ans to 0 int ans = (A == 1) ? 0 : 1; // Traversing across all the divisors of N // which are less than N for (int i = 1; i * i <= N; i++) { // Check if current value of // i is a divisor of N if (N % i == 0) { // Check if it is player A's turn // then we need at least one true if (A == 1) ans |= divisorGame(N - i, 0, dp); // Else if it is player B's turn // then we need at least one false else ans &= divisorGame(N - i, 1, dp); } } // Return the current ans return dp[N][A] = ans; } // Driver code public static void main(String[] args) { // Initialise N int N = 3; int[][] dp = new int[N + 1][2]; for (int i = 0; i < N + 1; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = -1; } } if (divisorGame(N, 1, dp) == 1) System.out.print("Player A wins"); else System.out.print("Player B wins"); } } // This code contributed by sapnasingh4991 # Python3 program for implementation of # Optimal Strategy for the Divisor # Game using Dynamic Programming from math import sqrt # Recursive function to find the winner def divisorGame(N,A,dp): # check if N=1 or N=3 then player B wins if (N == 1 or N == 3): return False # check if N=2 then player A wins if (N == 2): return True # check if current state already visited # then return the previously obtained ans if (dp[N][A] != -1): return dp[N][A] # check if currently it is player A's turn # then initialise the ans to 0 if(A == 1): ans = 0 else: ans = 1 # Traversing across all the divisors of N # which are less than N for i in range(1,int(sqrt(N))+1,1): # check if current value of # i is a divisor of N if (N % i == 0): # check if it is player A's turn # then we need at least one true if (A): ans |= divisorGame(N - i, 0, dp) # Else if it is player B's turn # then we need at least one false else: ans &= divisorGame(N - i, 1, dp) dp[N][A] = ans # Return the current ans return dp[N][A] # Driver code if __name__ == '__main__': # initialise N N = 3 dp = [[-1 for i in range(2)] for j in range(N+1)] if (divisorGame(N, 1, dp) == True): print("Player A wins") else: print("Player B wins") # This code is contributed by Surendra_Gangwar // C# program for implementation of // optimal strategy for the divisor // game using dynamic programming using System; class GFG { // Recursive function to find the winner static int divisorGame(int N, int A, int [,]dp) { // Check if N = 1 or N = 3 // then player B wins if (N == 1 || N == 3) return 0; // Check if N = 2 then player A wins if (N == 2) return 1; // Check if current state already visited // then return the previously obtained ans if (dp[N, A] != -1) return dp[N, A]; // Check if currently it is player A's turn // then initialise the ans to 0 int ans = (A == 1) ? 0 : 1; // Traversing across all the divisors of N // which are less than N for(int i = 1; i * i <= N; i++) { // Check if current value of // i is a divisor of N if (N % i == 0) { // Check if it is player A's turn // then we need at least one true if (A == 1) ans |= divisorGame(N - i, 0, dp); // Else if it is player B's turn // then we need at least one false else ans &= divisorGame(N - i, 1, dp); } } // Return the current ans return dp[N, A] = ans; } // Driver code public static void Main(String[] args) { // Initialise N int N = 3; int[,] dp = new int[N + 1, 2]; for(int i = 0; i < N + 1; i++) { for(int j = 0; j < 2; j++) { dp[i, j] = -1; } } if (divisorGame(N, 1, dp) == 1) { Console.Write("Player A wins"); } else { Console.Write("Player B wins"); } } } // This code is contributed by amal kumar choubey <script> // Javascript program for implementation of // Optimal Strategy for the Divisor // Game using Dynamic Programming // Recursive function to find the winner function divisorGame(N, A, dp) { // check if N=1 or N=3 then player B wins if (N == 1 || N == 3) return false; // check if N=2 then player A wins if (N == 2) return true; // check if current state already visited // then return the previously obtained ans if (dp[N][A] != -1) return dp[N][A]; // check if currently it is player A's turn // then initialise the ans to 0 let ans = (A == 1) ? 0 : 1; // Traversing across all the divisors of N // which are less than N for (let i = 1; i * i <= N; i++) { // check if current value of // i is a divisor of N if (N % i == 0) { // check if it is player A's turn // then we need at least one true if (A) ans |= divisorGame(N - i, 0, dp); // Else if it is player B's turn // then we need at least one false else ans &= divisorGame(N - i, 1, dp); } } // Return the current ans return dp[N][A] = ans; } // Driver code // initialise N let N = 3; let dp = []; for (let i = 0; i < N + 1; i++) { let temp = [-1] for (let j = 0; j < 2; j++) { temp.push([-1]) } dp.push(temp) } // memset(dp, -1, sizeof(dp)); if (divisorGame(N, 1, dp) == true) document.write("Player A wins"); else document.write("Player B wins"); // This code is contributed by gfgking </script> Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Similar Reads
Dynamic Programming in Game Theory for Competitive Programming In the fast-paced world of competitive programming, mastering dynamic programming in game theory is the key to solving complex strategic challenges. This article explores how dynamic programming in game theory can enhance your problem-solving skills and strategic insights, giving you a competitive e
15+ min read
Optimal Strategy for a Game Given an array arr[] of size n which represents a row of n coins of values V1 . . . Vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of
15+ min read
Optimal Strategy for a Game | Set 2 Problem statement: Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine
15+ min read
Optimal Strategy for a Game | Set 3 Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possibl
15+ min read
Optimal Strategy for the Divisor game using Dynamic Programming Given an integer N and two players, A and B are playing a game. On each player’s turn, that player makes a move by subtracting a divisor of current N (which is less than N) from current N, thus forming a new N for the next turn. The player who does not have any divisor left to subtract loses the gam
9 min read
Game of N stones where each player can remove 1, 3 or 4 Given an integer n. Two players are playing a game with pile of n stones, Player1 and Player2. Player1 and Player2 take turns with Player1 starting first. At each turn, a player can remove 1, 3 or 4 stones from the pile. The game ends when there is no stone left in the pile and the player who made t
9 min read
Find the player who will win by choosing a number in range [1, K] with sum total N Given two integers k and n. Two players are playing a game with these two numbers, Player1 and Player2. Player1 and Player2 take turns with Player1 starting first. At each turn, a player can choose a number in the range 1 to k, both inclusive and subtract the chosen value from n. The game ends when
6 min read
Find the winner of the game with N piles of boxes Given an array of strings arr[] of size n representing n piles containing white (W) and Black (B) boxes. Two players are playing a game with these piles, Player1 and Player2. Both take turns with Player1 starting first. In their respective turn, Player1 can remove any number of boxes from the top of
5 min read
Coin game of two corners (Greedy Approach) Consider a two-player coin game where each player gets turned one by one. There is a row of even a number of coins, and a player on his/her turn can pick a coin from any of the two corners of the row. The player that collects coins with more value wins the game. Develop a strategy for the player mak
9 min read