Is Find the Winning Player in Coin Game easy or hard?

Find the Winning Player in Coin Game is classified as an Easy problem. Once you notice that each move consumes a fixed number of coins, the game reduces to counting the total possible moves and checking whether that number is odd or even.

Find the Winning Player in Coin Game Python/Java solution

The implementation is very small in Python or Java. Calculate k = min(x, y // 4) and return "Alice" if k % 2 == 1, otherwise return "Bob". The logic is identical across languages since it only involves arithmetic operations.

How to solve Find the Winning Player in Coin Game in O(1)?

Compute the maximum number of valid moves as k = min(x, y // 4). Since players alternate turns starting with Alice, the winner depends on the parity of k. If k is odd, Alice performs the last move and wins; if k is even, Bob wins.

What is the best approach for Find the Winning Player in Coin Game?

The optimal solution uses a greedy mathematical observation. Each move removes 1 coin from the first pile and 4 coins from the second, so the total number of possible moves is min(x, y // 4). If this count is odd, Alice wins; if it is even, Bob wins. This approach runs in O(1) time and O(1) space.

Is Find the Winning Player in Coin Game asked at Google/Amazon/Meta?

Problems based on simple game theory and parity analysis are common in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the pattern of reducing a turn-based game to a mathematical observation appears frequently.

What data structure is used in Find the Winning Player in Coin Game?

No complex data structure is required. The solution relies on basic arithmetic operations and a parity check. The problem mainly tests math reasoning and game theory rather than data structure usage.

What is the time complexity of Find the Winning Player in Coin Game?

The optimal solution runs in O(1) time because it only computes min(x, y // 4) and checks whether the result is odd or even. A direct simulation approach would take O(k) time where k is the number of possible moves.

Description Hints 3 Solution Video 3:53

3222. Find the Winning Player in Coin Game

Easy53.9% acceptance1 company

You are given two positive integers x and y, denoting the number of coins with values 75 and 10 respectively.

Alice and Bob are playing a game. Each turn, starting with Alice, the player must pick up coins with a total value 115. If the player is unable to do so, they lose the game.

Return the name of the player who wins the game if both players play optimally.

Example 1:

Input: x = 2, y = 7

Output: "Alice"

Explanation:

The game ends in a single turn:

Alice picks 1 coin with a value of 75 and 4 coins with a value of 10.

Example 2:

Input: x = 4, y = 11

Output: "Bob"

Explanation:

The game ends in 2 turns:

Alice picks 1 coin with a value of 75 and 4 coins with a value of 10.
Bob picks 1 coin with a value of 75 and 4 coins with a value of 10.

Constraints:

1 <= x, y <= 100

Asked at 1 company

Bloomberg

Topics

Hints open one at a time

Hint 1

The only way to make 115 is to use one coin of value 75 and four coins of value 10. Each turn uses up these many coins.

Hint 2

Hence the number of turns is min(x, y / 4).

Hint 3

Determine the winner from its parity.

3:53

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution