 New update is available. Click here to update.

# Coin game winner where every player has three choices

Last Updated: 8 Mar, 2021
Difficulty: Moderate

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

##### 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
`````` ## Approach 1

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’.
SIMILAR PROBLEMS

JUMP GAME

Posted: 8 Sep, 2022
Difficulty: Moderate

NINJA AND HAPPINESS

Posted: 9 Sep, 2022
Difficulty: Hard

DECODE STRING

Posted: 11 Sep, 2022
Difficulty: Moderate

Randomly Sorted

Posted: 13 Nov, 2022
Difficulty: Moderate

8-Queen Problem

Posted: 19 Dec, 2022
Difficulty: Easy