New update is available. Click here to update.

Last Updated: 8 Mar, 2021

Difficulty: Moderate

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

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

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 10^5
Time limit: 1 sec
```

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’**.

The idea is to use a dynamic programming paradigm to improve the previous approach and see who wins the game. ‘**X’** starts the game and has 3 options, to take ‘**A’ **coins** or ‘B’ **coins** or 1** coin. Similarly, ‘**Y’** makes a move and so on. The player who is not able to move further loses the coin game. After each step, we cache the result. And now we are going to use this cached result to avoid solving the same subproblem more than once.

Let’s say if we have some ‘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, we can reach a point from where the other player cannot win we return true otherwise we return false.

The algorithm is as follows :

- Let’s define an array ‘CACHE‘ of length ‘N+1’ with all elements initialized to ‘-1’, to store the results of the subproblems.
**CACHE[i]**will store whether the player starting the game with ‘**i’**coins will win the game or not. - Declare a function
**FIND_WINNER()**which takes two argument ‘**NO_OF_COINS’**and an array ‘**CACHE’**, where ‘**NO_OF_COINS’**represents 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. - Check if
**CACHE[NO_OF_COINS] != -1**, then return**CACHE[NO_OF_COINS]**since we have already solved the problem for “NO_OF_COINS” coins and we don’t need to solve the same subproblem again. - 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.- Set,
**CACHE[NO_OF_COINS]**to**‘ANS’.** - Return the
**‘ANS’**.

The idea is to use a dynamic programming paradigm, 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. We solve in a bottom-up manner from **0 to 'NO_OF_COINS'** coins and calculate our ans.

Let’s say if we have some **i** 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, 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 boolean array ‘
**DP’**, where**DP[i]**stores the player starting with ‘**i’**coins wins the game or not, if the player starting with ‘**i’**coins wins it stores true, otherwise false. - Set,
**DP[0]**to**false**. - Set,
**DP[1]**to**true**. - Iterate from ‘
**i’ = 2 to ‘N’**,- Set,
**DP[i]**to**ans**to true if**DP[i - 1]**is**.** - If ‘
**i’ >= ‘A’**, set**DP[i]**to true if**DP[i - A]**is - If ‘
**i’ >= ‘B’**, set**DP[i]**to true if**DP[i - B]**is false.

- Set,
- Return,
**DP[N]**.

Popular Interview Problems: