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[0] = false;
        dp[1] = 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));
    }
}