algoadvance

Leetcode 3222. Find the Winning Player in Coin Game

Problem Statement

Two players are playing a game with n coins. The players take turns alternately, and each player must take at least 1 coin but not more than k coins on their turn. The player who takes the last coin wins the game.

Given the number of coins n and the maximum number of coins a player can take on their turn k, determine who the winning player is if both players play optimally, assuming that Player 1 always starts the game.

Return true if Player 1 can guarantee a win, and false if Player 2 can guarantee a win.

Example

  1. Input: n = 4, k = 2 Output: true

  2. Input: n = 5, k = 2 Output: false

Clarifying Questions

  1. Q: What happens if n or k is zero or negative?
    • A: Invalid input. n and k are always positive integers.
  2. Q: What is the maximum value for n and k?
    • A: Assume the values of n and k can be up to 10^6.
  3. Q: If k >= n, is the winner immediately determined?
    • A: Yes, Player 1 can take all the coins and win if k >= n.

Strategy

We will use dynamic programming to determine the winning strategy:

  1. Create a boolean array dp where dp[i] indicates whether Player 1 can guarantee a win with i coins remaining.
  2. If i <= k, dp[i] is true because Player 1 can take all i coins and win.
  3. For i > k, dp[i] will be true if there exists an x (1 <= x <= k) such that dp[i - x] is false. This means Player 1 can leave Player 2 in a losing position after Player 1 takes x coins.

Time Complexity

The time complexity of the solution is O(n * k), where we iterate over the dp array up to n and, for each position i, potentially check up to k values.

Code

public class CoinGame {
    public boolean canPlayerOneWin(int n, int k) {
        if (k >= n) {
            return true;
        }
        
        boolean[] dp = new boolean[n + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (i - j >= 0 && !dp[i - j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        CoinGame game = new CoinGame();
        
        // Test cases
        System.out.println(game.canPlayerOneWin(4, 2)); // true
        System.out.println(game.canPlayerOneWin(5, 2)); // false
    }
}

This code sets up the problem using dynamic programming. The boolean array dp is used to store the result for each number of coins from 0 to n. The nested loops populate this array based on the conditions defined. When the program runs, it outputs whether Player 1 can secure a win with optimal play for the given n and k.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI