Coin game winner where every player has three choices
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

Question

Coin game winner where every player has three choices

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

Accepted Answer

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 false.
If ‘i’ >= ‘A’, set DP[i] to true if DP[i - A] is false.
If ‘i’ >= ‘B’, set DP[i] to true if DP[i - B] is false.
Return, DP[N].

Accepted Answer

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

Space Complexity: O(n)Explanation:

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

Time Complexity: O(3^n)Explanation:

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

Accepted Answer

Dynamic Programming

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

Space Complexity: O(n)Explanation:

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

Time Complexity: O(n)Explanation:

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

Here we are trying all possible options, at each step we have three options. But we don’t solve any subproblem more than once. So, the overall time complexity is O(N).

C++ (g++ 5.4)

/*
    Time Complexity : O(N)
    Space Complexity : O(N)

    where, where 'N' is the number of coins.
*/

// Find the winner
bool findWinner(int noOfCoins, int a, int b, vector &cache)
{

    // If noOfCoins = 0, then return false, since we don’t have any coins.
    if (noOfCoins == 0)
    {
        return false;
    }

    if (cache[noOfCoins] != -1) 
    {
        return cache[noOfCoins];
    }

    bool ans = false;

    // Trying all three options.
    if (noOfCoins >= a && !findWinner(noOfCoins - a, a, b, cache))
    {
        ans = true;
    }

    if (noOfCoins >= b && !findWinner(noOfCoins - b, a, b, cache))
    {
        ans = true;
    }

    if (noOfCoins >= 1 && !findWinner(noOfCoins - 1, a, b, cache))
    {
        ans = true;
    }

    cache[noOfCoins] = ans;

    // Return the ans.
    return ans;
}

// Returns whether X is the winner or not.
int coinGameWinner(int n, int a, int b)
{
    vector cache(n + 1, -1);

    bool ans = findWinner(n, a, b, cache);

    // Return the ans.
    return ans;
}

Java (SE 1.8)

/*
    Time Complexity : O(N)
    Space Complexity : O(N)

    where, where 'N' is the number of coins.
*/


public class Solution {
    // Find the winner
    public static int findWinner(int noOfCoins, int a, int b, int[] cache)
    {

        // If noOfCoins = 0, then return false, since we don't have any coins.
        if (noOfCoins == 0)
        {
            return 0;
        }

        if (cache[noOfCoins] != -1) 
        {
            return cache[noOfCoins];
        }

        int ans = 0;

        // Trying all three options.
        if (noOfCoins >= a && findWinner(noOfCoins - a, a, b, cache) == 0)
        {
            ans = 1;
        }

        if (noOfCoins >= b && findWinner(noOfCoins - b, a, b, cache) == 0)
        {
            ans = 1;
        }

        if (noOfCoins >= 1 && findWinner(noOfCoins - 1, a, b, cache) == 0)
        {
            ans = 1;
        }

        cache[noOfCoins] = ans;

        // Return the ans.
        return ans;
    }

    // Returns whether X is the winner or not.
    public static int coinGameWinner(int n, int a, int b) {
        int[] cache = new int[n + 1];
        for(int i=0;i            cache[i] = -1;
        }

        int ans = findWinner(n, a, b, cache);

        // Return the ans.
        return ans;
    }
}

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)



    where N is the number of coins.

'''



# Find the winner.

def findWinner(noOfCoins, a, b, cache):



    # If noOfCoins = 0, then return false, since we donâ€™t have any coins.

    if (noOfCoins == 0):

        return False



    if (cache[noOfCoins] != -1):

        return cache[noOfCoins]



    ans = False



    # Trying all three options.

    if (noOfCoins >= a and not findWinner(noOfCoins - a, a, b, cache)):

        ans = True



    if (noOfCoins >= b and not findWinner(noOfCoins - b, a, b, cache)):

        ans = True



    if (noOfCoins >= 1 and not findWinner(noOfCoins - 1, a, b, cache)):

        ans = True



    cache[noOfCoins] = ans



    # Return the ans.

    return ans





def coinGameWinner(n, a, b):

    cache = [-1 for i in range(n + 1)]



    ans = findWinner(n, a, b, cache)



    # Return the ans.

    return int(ans)

Accepted Answer

Dynamic Programming

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 false.
- If ‘i’ >= ‘A’, set DP[i] to true if DP[i - A] is false.
- If ‘i’ >= ‘B’, set DP[i] to true if DP[i - B] is false.
Return, DP[N].

Space Complexity: O(n)Explanation:

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

Since we are using a dp array of order ‘N’. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

Here we are iterating from ‘i’ = 2 to ‘N’, which is of order ‘N’. So, the overall time complexity is O(N).

Java (SE 1.8)

/*
    Time Complexity : O(N)
    Space Complexity : O(N)

    where 'N' is the number of coins.
*/

public class Solution {
	// Returns whether X is the winner or not.
    public static int coinGameWinner(int n, int a, int b) {
        int[] dp = new int[n + 1];
		dp[0] = 0;
		dp[1] = 1;

		for (int i = 2; i <= n; i++)
		{
			// Checking all three cases.
			if (dp[i - 1] == 0)
			{
				dp[i] = 1;
			}

			if (i >= a && dp[i - a] == 0)
			{
				dp[i] = 1;
			}

			if (i >= b && dp[i - b] == 0)
			{
				dp[i] = 1;
			}
		}

		// Return the ans.
		return dp[n];
    }
}

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)



    where 'N' is the number of coins.

'''



# Returns whether X is the winner or not.

def coinGameWinner(n, a, b):



    dp = [False for i in range(n + 1)]

    dp[1] = True



    for i in range(2, n + 1):

        # Checking all three cases.

        if (not dp[i - 1]):

            dp[i] = True



        if (i >= a and not dp[i - a]):

            dp[i] = True



        if (i >= b and not dp[i - b]):

            dp[i] = True



    # Return the ans.

    return int(dp[n])

C++ (g++ 5.4)

/*
    Time Complexity : O(N)
    Space Complexity : O(N)

    where 'N' is the number of coins.
*/

// Returns whether X is the winner or not.
int coinGameWinner(int n, int a, int b)
{

	vector dp(n + 1);
	dp[0] = 0;
	dp[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		// Checking all three cases.
		if (!dp[i - 1])
		{
			dp[i] = 1;
		}

		if (i >= a && !dp[i - a])
		{
			dp[i] = 1;
		}

		if (i >= b && !dp[i - b])
		{
			dp[i] = 1;
		}
	}

	// Return the ans.
	return dp[n];
}

Input Format

Output Format:

Note :

Constraints:

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer