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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Winning Player in Coin Game

Number: 3511

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given two positive integers x and y representing the number of coins with values 75 and 10 respectively, Alice and Bob play a game. Starting with Alice, each player takes turns to pick coins with a total value of 115. Each valid turn strictly requires picking 1 coin of value 75 and 4 coins of value 10 (since 75 + 4*10 = 115). If a player cannot make such a move, that player loses. Determine the winner if both players play optimally.

Key Insights

  • A valid move always uses 1 coin of 75 and 4 coins of 10.
  • The maximum number of moves possible is determined by the limiting resource: moves = min(x, y // 4).
  • If the total moves possible is odd, Alice (the first player) wins, otherwise Bob wins.
  • If no move is possible (i.e. moves == 0), then Alice loses immediately and Bob wins.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

Use a straightforward arithmetic approach:

  1. Calculate the maximum moves possible using moves = min(x, y // 4).
  2. Check if the moves count is odd; if yes, Alice wins, otherwise Bob wins. This algorithm uses simple math operations on integers, ensuring optimal time and space efficiencies.

Code Solutions

# Python solution
def find_winner(x: int, y: int) -> str:
    # Calculate the maximum number of moves possible
    moves = min(x, y // 4)
    # If the number of moves is odd, Alice wins; otherwise, Bob wins.
    return "Alice" if moves % 2 == 1 else "Bob"

# Example usage
if __name__ == "__main__":
    x, y = 2, 7  # Example 1
    print(find_winner(x, y))  # Output: Alice

    x, y = 4, 11  # Example 2
    print(find_winner(x, y))  # Output: Bob
← Back to All Questions