Coin game winner where every player has three choices

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
31 upvotes
Asked in companies
OlaNagarro Software

Problem statement

Two players 'X' and 'Y', are playing a coin game. Initially, there are 'N' coins. Each player can pick exactly 'A' coins or 'B' coins or 1 coin. A player loses the game if he is not able to pick any coins. 'X' always starts the game, and each player plays optimally. You are supposed to find which player wins the coin game.

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ representing the number of test cases.

The first line of each test case contains three integers: ‘N’ denoting the number of coins, integer ‘A’, integer ‘B’ denoting the number of coins each player can take in a turn.
Output Format: 
For each test case, return one integer 0 or 1. return 1, if X wins the coin game, or return 0, if Y wins the coin game.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^5

Time limit: 1 sec
Sample Input 1:
2
5 3 4
4 2 3
Sample Output 1:
1
0
Explanation for Sample Input 1:
For the first test case, There are 5 coins, every player can pick 1 or 3 or 4 coins on his/her turn. X picks 3 coins in the first turn, now the remaining coins are 2, Y can only pick 1 coin. So, X wins by picking the last coin.

For the second test case, No, matter what coins X picks, Y always wins.
Sample Input 2:
2
8 2 4
9 3 4
Sample Output 2:
1
0
Hint

Try every possible option.

Approaches (3)
BruteForce

The idea is to try every possible option, and see who wins the game. ‘X’ start’s the game and has 3 options, to choose ‘A’ or ‘B’ or 1 coin. Similarly, ‘Y’ makes a move and so on. The player who is not able to move further loses the coin game. 

Let’s denote the total coins we have by NO_OF_COINS, and Player X is playing the game, X will always try to reach a point from where Y cannot win. So, we are checking all three options which X can reach, and if we can reach a point from where the other player cannot win we return true otherwise we return false.

 

The algorithm is as follows :

  • Declare a function FIND_WINNER() which takes an argument ‘NO_OF_COINS’, representing the coins we have initially and it returns true if a player starting the game with ‘NO_OF_COINS’ coins will win, otherwise, it returns false.
  • If ‘NO_OF_COINS’ = 0, then return false, since we don’t have any coins.
  • Declare a boolean variable ‘ANS’ to false.
  • Finally, try all three options.
  • If, ‘NO_OF_COINS >= A’, initialize ‘ANS’ to true if the value returned by  FIND_WINNER(NO_OF_COINS - A) is false.
  • If ‘NO_OF_COINS’ >= ‘B’, set ‘ANS’ to true if the value returned by FIND_WINNER(NO_OF_COINS - B)  is false.
  • If ‘NO_OF_COINS’ >= 1, set ‘ANS’ to true if the value returned by  FIND_WINNER(NO_OF_COINS - 1) is false.
  • Return the ‘ANS’.
Time Complexity

O(3^N), where ‘N’ is the number of coins.

 

Here we are trying all possible options, at each step we have three options. The number of function calls done are in the order of 3^N. So, the overall time complexity is O(3^N).

Space Complexity

O(N), where ‘N’ is the number of coins.

 

The maximum recursive stack can grow up to the order of ‘N’. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Coin game winner where every player has three choices
Full screen
Console