Alice and Bob Playing Flower Game - Video Solutions

Problem Overview: You are given two integers n and m representing the number of flowers Alice and Bob can pick. Alice chooses x from 1..n and Bob chooses y from 1..m. Alice wins if x + y is odd. The task is to count how many pairs (x, y) lead to Alice winning.

Approach 1: Brute Force Pair Enumeration (O(n * m) time, O(1) space)

The most direct solution iterates through every possible pair of choices. Use two nested loops: the outer loop picks x from 1..n and the inner loop picks y from 1..m. For each pair, compute (x + y) % 2 and increment the count when the sum is odd. This approach clearly demonstrates the game condition but performs unnecessary checks when n and m are large. It works as a baseline but does not scale well.

Approach 2: Using a Stack to Manage State (O(n + m) time, O(n) space)

A stack can be used to track parity states of Alice's choices. Push all values from 1..n onto a stack and pop each value while determining whether it is odd or even. For each popped value, count how many compatible values Bob can choose so that the total sum becomes odd. If x is odd, Bob must choose an even number; if x is even, Bob must choose an odd number. Precompute the counts of odd and even numbers in 1..m. The stack itself is not strictly required but demonstrates state management in iterative simulations.

Approach 3: Using Recursion to Simplify State Management (O(n) time, O(n) space)

Recursion can process Alice's choices one at a time. Define a recursive function that evaluates the current value of x and adds the number of valid y values based on parity. The recursion moves from x = 1 to x = n, accumulating valid combinations. Similar to the stack approach, the key observation is parity compatibility: odd pairs with even produce odd sums. While recursion simplifies control flow, it adds call stack overhead and is rarely the most efficient implementation.

Approach 4: Mathematical Parity Counting (O(1) time, O(1) space)

The optimal solution uses simple math and combinatorics. An odd sum occurs only when one number is odd and the other is even. Count how many odd and even numbers exist in each range. In 1..n, odd count is (n + 1) / 2 and even count is n / 2. In 1..m, odd count is (m + 1) / 2 and even count is m / 2. Valid winning pairs are odd_x * even_y + even_x * odd_y. This eliminates iteration entirely and runs in constant time using basic parity math.

Recommended for interviews: Start by describing the brute force approach to show you understand the condition for Alice winning. Then move to the mathematical parity insight. Interviewers typically expect the constant-time counting method because it demonstrates pattern recognition and efficient use of number properties.