Given an integer N, the task for two players A and B is to make the value of X ( initialized with 1) at least N by multiplying X with any number from the range [2, 9] in alternate turns. Assuming both players play optimally. the task is to find the player to obtain a value ? N first.
Examples:
Input: N = 12
Output: Player B
Explanation:
Initially, X = 1.
A multiplies X with 9. Therefore, X = 1 * 9 = 9.
In second turn, B multiplies X with 2. Therefore, X = 9*2 = 18
Therefore, B wins.Input: N = 10
Output: Player B
Approach: The idea is to use the concept of combinatorial game theory. Find the positions from where, if a number is multiplied with X leads to victory and also the positions which lead to a loss. Below are the steps:
- In combinatorial game theory, let’s define that an N position is a position from which the next player to move wins if he plays optimally and P-position is a position where the next player to move always loses if his opponent plays optimally.
- The lowest position that can be reached up to N is, say res = ceil(N/9). Therefore, all the positions from [res, res + 1, res + 2, ….., N – 1] are N positions.
- The only positions that are forced to move to [res, res + 1, …, (N – 1)] are those that when multiplied by 2, and they lie in that interval, which is given by Y = ceil(res/2),
- Therefore, [Y, Y + 1, …, (res – 1)] are all the P-positions.
- After repeating the above steps until the interval containing 1 is found if 1 is an N-position then A wins, else B wins.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the winnerchar Winner(int N){ bool player = true; // Backtrack from N to 1 while(N > 1) { int den = (player) ? 9 : 2; int X = N/den, Y = N%den; N = (Y)? X + 1: X; player = !player; } if (player) return 'B'; else return 'A';}// Driver Codeint main(){ int N = 10; cout << Winner(N); return 0;}// This code is contributed by mohit kumar 29. |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the winner static char Winner(int N) { boolean player = true; // Backtrack from N to 1 while(N > 1) { int den = (player) ? 9 : 2; int X = N / den; int Y = N % den; N = (Y > 0) ? X + 1: X; player = !player; } if (player) return 'B'; else return 'A'; } // Driver Code public static void main(String[] args) { int N = 10; System.out.print(Winner(N)); }}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to find the winnerdef Winner(N): player = True # Backtrack from N to 1 while N > 1: X, Y = divmod(N, (9 if player else 2)) N = X + 1 if Y else X player = not player if player: return 'B' else: return 'A'# Driver CodeN = 10print(Winner(N)) |
C#
// C# program for the above approachusing System;class GFG { // Function to find the winner static char Winner(int N) { bool player = true; // Backtrack from N to 1 while (N > 1) { int den = (player) ? 9 : 2; int X = N / den; int Y = N % den; N = (Y > 0) ? X + 1 : X; player = !player; } if (player) return 'B'; else return 'A'; } // Driver Code static public void Main() { int N = 10; Console.WriteLine(Winner(N)); }}// This code is contributed by Dharanendra L V |
Javascript
<script>// Javascript program for the above approachfunction Winner(N){ var player = Boolean(true); // Backtrack from N to 1 while(N > 1) { var den = (player) ? 9 : 2; var X = parseInt(N/den), Y = parseInt(N%den); N = (Y)? X + 1: X; player = !player; } if (player) document.write( 'B'); else document.write( 'A');}var N = 10;Winner(N);// This code is contributed by SoumikMondal</script> |
B
Time Complexity: O(log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!