algoadvance

Leetcode 3222. Find the Winning Player in Coin Game

Problem Statement

In this problem, two players alternately take 1, 2, or 3 coins from a pile of n coins. The player who takes the last coin wins the game. Assuming both players play optimally, you need to determine if the first player is guaranteed to win. If the first player wins, return true; otherwise, return false.

Clarifying Questions

  1. How many coins are initially in the pile?
    • The number n represents the initial number of coins.
  2. What is the range of n?
    • Typically n is a non-negative integer and can be as large as 10^9.
  3. Do we need to consider edge cases like n being zero or negative?
    • Generally, n is assumed to be non-negative.

Strategy

To determine if the first player will win, consider the following thoughts:

  1. If n is 0, then the game does not proceed, and neither player wins.
  2. For small values of n (from 1 to 3), the first player can just take all the remaining coins and win.
  3. For larger values, if the first player leaves a multiple of 4 (i.e., 4, 8, 12, ...) coins for the second player, the second player will lose if the first player continues to play optimally. This is because the second player can’t avoid leaving some subsequent non-multiple of 4 for the first player, which allows the first player to eventually leave the second player with another multiple of 4.

Conclusion:

Code

class Solution {
public:
    bool canWinCoinGame(int n) {
        return n % 4 != 0;
    }
};

Time Complexity

This solution runs in constant time O(1) since it only involves a modulus operation and a comparison.

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