Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every turn removes exactly one flower, so the game always lasts x + y turns regardless of which lane is chosen. Alice takes the odd-numbered turns and wins precisely when this total is odd. That happens when one lane has an odd number of flowers and the other has an even number.

Approach

Among the integers from one through n, there are floor(n / 2) even choices and floor(n / 2) + n % 2 odd choices. Compute the analogous counts for m.

Multiply the odd choices in the first range by the even choices in the second, then add the even-first, odd-second product. These two cases are disjoint and cover every pair with an odd total, so their sum is exactly the number of winning pairs.

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        # en = n // 2
        # on = n // 2
        # if n % 2 != 0: on += 1
        # em = m // 2
        # om = m // 2
        # if m % 2 != 0: om += 1
        # return (on * em) + (en * om)

        return (
            (m // 2 * (n // 2 + (n % 2))) +
            (n // 2 * (m // 2 + (m % 2)))
        )

Complexity analysis

Time: O(1). Auxiliary space: O(1).