## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Coin in Line

Sharing is caring!

##### Problem Statement
A and B are playing a game. At the beginning there are n coins. Given two more numbers x and y. In each move a player can pick x or y or 1 coins. A always starts the game. The player who picks the last coin wins the game. For a given value of n, find whether A will win the game or not if both are playing optimally.
##### Solution
We use dynamic programming (DP). If A lost in the game with i-1 (dp[i-1] == false), it means that B could come up with a strategy that leaves a value V with max(1,x,y)<V<=min(1,x,y) + max(1,x,y) in the second-to-last move for A. That way even if A would pick the least amount of coin (min(1,x,y)) in order to leave a maximum leftover for B, the leftover for B would be smaller than 1 or x or y, making B the winner. Now, if we consider i (one unit greater than i-1) this means that B would not be able to perform the above mentioned move in the second-to last step, thus letting A win.
``````public class CoinInLine {

public static boolean solve(int n, int x, int y) {
boolean[] dp = new boolean[n+1];
dp = false;
dp = true;

for (int i=2; i<=n; i++) {
if (i-1>=0 && dp[i-1] == false) {
dp[i] = true;
} else if (i-x>=0 && dp[i-x] == false) {
dp[i] = true;
} else if (i-y>=0 && dp[i-y] == false) {
dp[i] = true;
} else {
dp[i] = false;
}
}

return dp[n];
}

public static void main(String[] args) {
System.out.println(solve(5, 3, 4));
}
}``````