Coin game winner where every player has three choices

The problem, simply

There is a pile of n coins and two players, A and B. A goes first. On a turn, a player must take exactly 1, x or y coins (only if the pile has that many). The player who takes the last coin wins.

Both players are perfect: they always pick the best move. Say who wins, A or B.

A story to remember it

Picture it

Examples

Way 1: the simple way

Ask "can the player to move win with n coins?" with recursion.

1. If n == 0, the player to move has lost. Return false.
2. Try taking 1, x and y (if there are enough coins).
3. If any move leaves a pile where the other player cannot win, return true.
4. If none does, return false.

class Solution {
    // can the player who moves now win with n coins left?
    boolean canWin(int n, int x, int y) {
        if (n == 0) return false;                    // the other player took the last coin
        int[] moves = {1, x, y};
        for (int m : moves) {
            if (m <= n && !canWin(n - m, x, y)) return true;   // leave a losing pile
        }
        return false;                                // every move helps the other player
    }

    public String findWinner(int n, int x, int y) {
        return canWin(n, x, y) ? "A" : "B";
    }
}

How long it takes: each call can make three more calls, so it can grow like O(3^n). Extra room: the chain of waiting calls is up to n long, O(n).

Way 2: the clever way

A pile size has the same answer every time it shows up, no matter who is moving. So write W or L for every pile size from 0 up to n, once.

1. win[0] = false.
2. For i from 1 to n: win[i] is true if win[i - 1], win[i - x] or win[i - y] is false (only for moves that fit).
3. If win[n] is true, A wins. Otherwise B wins.

class Solution {
    public String findWinner(int n, int x, int y) {
        boolean[] win = new boolean[n + 1];   // win[i]: player to move with i coins wins
        win[0] = false;                       // no coins: you already lost
        for (int i = 1; i <= n; i++) {
            // win if some move leaves the other player a losing pile
            if (!win[i - 1]) win[i] = true;
            else if (i >= x && !win[i - x]) win[i] = true;
            else if (i >= y && !win[i - y]) win[i] = true;
        }
        return win[n] ? "A" : "B";
    }
}

How long it takes: three checks per pile size, O(n). Extra room: one card per pile size, O(n). You only ever look back max(x, y) cards, so a ring of that size is enough if memory is tight.

Watch out for

• Check i >= x and i >= y before looking back, or you read outside the array.
• x or y can equal 1 or each other. The code still works, it just checks the same move twice.
• The answer says who wins, not how many coins were taken. Return "A" when win[n] is true.

What interviewers ask next

• Is there a pattern? Yes, the W and L marks always repeat after a while, because each mark only depends on the last max(x, y) marks. For moves 1, 2, 3 the losing piles are exactly the multiples of 4, so the answer is n % 4 != 0.
• What if the player who takes the last coin loses? Then a pile of 0 is a win for the player to move (the other player was forced to take the last coin). Start with win[0] = true and keep the same rule.
• Many piles at once, where you take from any one pile? That is Nim-style. You need Grundy numbers: for each pile size, the smallest number not reached by any move, and you XOR them.
• What about picking from either end of a row of coins with values? That is "Optimal strategy for a game", a different DP over ranges.

Remember this

Grown-up words: W and L are winning and losing positions, the dots and arrows are the game graph, "both play perfectly" is optimal play, and the repeating marks come from the sequence being periodic.