We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Winning Player in Coin Game

Difficulty: Easy

Problem Description

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.

Key Insights

  • Players take turns starting with Alice.
  • A player must collect coins summing up to 115 in value.
  • The only valid combinations to achieve 115 are:
    • 1 coin of 75 and 4 coins of 10 (1 * 75 + 4 * 10 = 115)
    • 2 coins of 75 and 1 coin of 10 (2 * 75 + 1 * 10 = 160, not valid)
    • No combination can exceed the available coins.
  • The game can be thought of as a simulation where players exhaust their options.

Space and Time Complexity

Time Complexity: O(1) - The solution involves simple arithmetic checks and does not depend on the size of input. Space Complexity: O(1) - Only a constant amount of space is used for variables.

Solution

To determine the winner, we can simulate the game by checking how many valid turns Alice and Bob can take. We will check if Alice can make a valid move first and then check if Bob can make a move in response. The game alternates until one player cannot make a valid move.

Code Solutions

def find_winning_player(x, y):
    # Calculate how many moves Alice can make
    alice_moves = min(x, y // 4)
    remaining_y = y - (alice_moves * 4)
    
    # Check if Alice can make a valid move
    if alice_moves > 0 and (remaining_y >= 0 or (x - alice_moves) > 0):
        # If Alice can make a move successfully, now check Bob's turn
        bob_moves = min(x - alice_moves, remaining_y // 4)
        if bob_moves > 0:
            return "Bob"  # Bob can move, so Alice loses
    return "Alice"  # If Bob cannot move, Alice wins

# Example usage
print(find_winning_player(2, 7))  # Output: "Alice"
print(find_winning_player(4, 11))  # Output: "Bob"
← Back to All Questions