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

Alice and Bob Playing Flower Game

Number: 3279

Difficulty: Medium

Paid? No

Companies: Rubrik

Problem Description

Alice and Bob play a turn-based game on a circular field surrounded by flowers. There are x flowers in the clockwise direction and y flowers in the anti-clockwise direction between them, where x is in the range [1, n] and y is in the range [1, m]. On each turn, the current player picks one flower from either side. The game ends at the end of a turn when all flowers have been picked, and the player who made that final move wins (by capturing the opponent). Given n and m, count the number of pairs (x, y) for which Alice wins the game if she makes the first move.

Key Insights

  • The game can be modeled as two piles of flowers with x and y flowers.

  • Each move removes exactly one flower from one of the two piles.

  • The game ends when both piles are empty, meaning exactly (x + y) moves occur.

  • Since Alice starts, she wins if (x + y) is odd (she takes the last turn), and loses if (x + y) is even.

  • Therefore, count pairs (x, y) such that x + y is odd.

  • Count odd numbers and even numbers in the interval [1, n] (for x) and [1, m] (for y) and use the relation:

    Number of valid pairs = (odd count in [1, n] * even count in [1, m]) + (even count in [1, n] * odd count in [1, m]).

Space and Time Complexity

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

Solution

This problem simplifies to counting pairs (x, y) with x + y being odd. We first compute the number of odd and even numbers available in [1, n] and [1, m]. For any integer k:

  • The number of odds is given by (k + 1) // 2.
  • The number of evens is given by k // 2.

Then the solution is:

validPairs = (odds in [1, n] * evens in [1, m]) + (evens in [1, n] * odds in [1, m]).

This mathematical derivation lets us compute the answer in constant time with basic arithmetic.

Code Solutions

# Python solution
def aliceWins(n: int, m: int) -> int:
    # Calculate the number of odds in [1, n]
    odd_n = (n + 1) // 2
    # Calculate the number of evens in [1, n]
    even_n = n // 2
    # Calculate the number of odds in [1, m]
    odd_m = (m + 1) // 2
    # Calculate the number of evens in [1, m]
    even_m = m // 2
    # Valid pairs: (odd in n * even in m) + (even in n * odd in m)
    return odd_n * even_m + even_n * odd_m

# Example usage:
print(aliceWins(3, 2))  # Expected output: 3
← Back to All Questions