Problem Statement in English

Alice and Bob are playing a game with flowers.

We’re allowed to have $1 <= x <= n$ for the first row of flowers, and $1 <= y <= m$ for the second row of flowers.

We need to calculate the number of $(x, y)$ pairs such that the sum of flowers in both rows is odd.

Approach

For Alice to win we need a pair $(x, y)$ such that $x + y$ is odd. This can happen in two scenarios:

  1. $x$ is odd and $y$ is even
  2. $x$ is even and $y$ is odd

So we just calculate the number of valid pairs for both scenarios and sum them up.

Solution in Python


class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        evens_in_n = n // 2
        odds_in_n = n - evens_in_n
        
        evens_in_m = m // 2
        odds_in_m = m - evens_in_m

        return odds_in_n * evens_in_m + evens_in_n * odds_in_m

Complexity

  • Time: $O(1)$
    Since we just run one calculation.

  • Space: $O(1)$
    Since we use no extra variables.

Mistakes I Made

I misread the question and thought the winner was the person on whose turn there are no flowers to pick 🤦‍♂️

And we are done.