Coin game winner where every player has three choices

Problem Statement

Two players are playing a coin game. There are n coins in a pile. Each player can pick 1, 2, or 3 coins in their turn. The player who picks the last coin wins. Both players play optimally. Determine which player wins — Player 1 or Player 2. Player 1 always goes first.

Example:

• Input: n = 5

• Output: Player 1

• Explanation: Player 1 picks 1 coin (4 left). No matter what Player 2 picks (1, 2, or 3), Player 1 can always pick the rest to win.

• Input: n = 4

• Output: Player 2

• Explanation: Whatever Player 1 picks (1, 2, or 3), Player 2 can pick the remaining to win.

Noob-Friendly Explanation

Imagine two friends sitting around a pile of coins. They take turns grabbing 1, 2, or 3 coins. Whoever grabs the last coin wins! Both friends are super smart and always make the best move.

The trick is: if there are 4 coins left and it's your turn, you're in trouble! No matter if you take 1, 2, or 3, your opponent takes the rest and wins. So the game depends on how many coins are left and whose turn it is.

Approach 1: Brute Force (Recursion)

Intuition

Simulate the game recursively. At each turn, the current player tries picking 1, 2, or 3 coins. If any choice leads to a losing position for the opponent, the current player wins.

Algorithm

1. A position with 0 coins is a losing position (the previous player took the last coin).
2. A player wins if they can move to a position where the opponent loses.
3. Recursively check all three choices.

class Solution {
    public String coinGameWinner(int n) {
        // true means the current player wins
        boolean player1Wins = canWin(n);
        return player1Wins ? "Player 1" : "Player 2";
    }

    private boolean canWin(int n) {
        if (n <= 0) return false; // No coins left, current player loses

        // Try picking 1, 2, or 3 coins
        // If opponent loses after any of our moves, we win
        for (int pick = 1; pick <= 3; pick++) {
            if (n >= pick && !canWin(n - pick)) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

• Time Complexity: O(3^n) - Each call branches into 3 recursive calls.
• Space Complexity: O(n) - Recursion stack depth.

Approach 2: Optimal (Dynamic Programming / Pattern)

Intuition

If we compute the results for small values of n, a pattern emerges: the current player loses only when n is a multiple of 4. For all other values, the first player can always win. We can also solve this with a DP array.

Algorithm

1. Create a boolean array dp[0..n] where dp[i] = true if the current player wins with i coins.
2. dp[0] = false (no coins = lose).
3. For each i from 1 to n, dp[i] = true if any of dp[i-1], dp[i-2], or dp[i-3] is false (opponent is in a losing position).
4. Answer is dp[n].

class Solution {
    public String coinGameWinner(int n) {
        if (n <= 0) return "Player 2";

        boolean[] dp = new boolean[n + 1];
        dp[0] = false; // No coins = current player loses

        for (int i = 1; i <= n; i++) {
            // Current player wins if they can put opponent in a losing spot
            dp[i] = false;
            for (int pick = 1; pick <= 3 && pick <= i; pick++) {
                if (!dp[i - pick]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n] ? "Player 1" : "Player 2";

        // Note: The pattern is simply n % 4 != 0 means Player 1 wins
        // return (n % 4 != 0) ? "Player 1" : "Player 2";
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass to fill the DP array.
• Space Complexity: O(n) - DP array of size n+1. Can be reduced to O(1) using the pattern n % 4 != 0.