Alice and Bob Playing Flower Game - Solution & Explanation
Problem Statement
Alice and Bob are playing a turn-based game on a circular field surrounded by flowers. The circle represents the field, and there are x flowers in the clockwise direction between Alice and Bob, and y flowers in the anti-clockwise direction between them.
The game proceeds as follows:
- Alice takes the first turn.
- In each turn, a player must choose either the clockwise or anti-clockwise direction and pick one flower from that side.
- At the end of the turn, if there are no flowers left at all, the current player captures their opponent and wins the game.
Given two integers, n and m, the task is to compute the number of possible pairs (x, y) that satisfy the conditions:
- Alice must win the game according to the described rules.
- The number of flowers
xin the clockwise direction must be in the range[1,n]. - The number of flowers
yin the anti-clockwise direction must be in the range[1,m].
Return the number of possible pairs (x, y) that satisfy the conditions mentioned in the statement.
Example 1:
Input: n = 3, m = 2 Output: 3 Explanation: The following pairs satisfy conditions described in the statement: (1,2), (3,2), (2,1).
Example 2:
Input: n = 1, m = 1 Output: 0 Explanation: No pairs satisfy the conditions described in the statement.
Constraints:
1 <= n, m <= 105
Approach Overview
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.
Approach 1: Approach 1: Using a Stack to Manage State
This approach uses a stack to efficiently manage and keep track of the states required to solve the problem. The stack data structure is ideal here due to its LIFO (Last In, First Out) nature, which allows for easy reversal and state management. This is useful in scenarios like parsing nested structures or evaluating expressions.
This C code implements a stack using an array. The push function adds an element to the top of the stack, and the pop function removes and returns the top element. Array-based stacks are straightforward but require a predefined maximum size.
Complexity
Time Complexity: O(1) for both push and pop operations.
Space Complexity: O(n) where n is the maximum stack size.
Approach 2: Approach 2: Using Recursion to Simplify State Management
This approach leverages recursion to handle the inherent hierarchical or nested nature of the problem. Recursive solutions are elegant and allow the function call stack to manage state, thus abstracting it away from the programmer.
This C code uses a recursive function to print numbers from n down to 1. Recursive calls decrement the counter n until the base case is reached, demonstrating a simple recursive pattern.
Complexity
Time Complexity: O(n) where n is the value passed to the function.
Space Complexity: O(n) due to the recursion call stack.
Approach 3: Mathematics
According to the problem description, in each move, the player will choose to move in a clockwise or counterclockwise direction and then pick a flower. Since Alice moves first, when x + y is odd, Alice will definitely win the game.
Therefore, the number of flowers x and y meet the following conditions:
x + yis odd;1 \le x \le n;1 \le y \le m.
If x is odd, y must be even. At this time, the number of values of x is \lceil \frac{n}{2} \rceil, the number of values of y is \lfloor \frac{m}{2} \rfloor, so the number of pairs that meet the conditions is \lceil \frac{n}{2} \rceil times \lfloor \frac{m}{2} \rfloor.
If x is even, y must be odd. At this time, the number of values of x is \lfloor \frac{n}{2} \rfloor, the number of values of y is \lceil \frac{m}{2} \rceil, so the number of pairs that meet the conditions is \lfloor \frac{n}{2} \rfloor times \lceil \frac{m}{2} \rceil.
Therefore, the number of pairs that meet the conditions is \lceil \frac{n}{2} \rceil times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor times \lceil \frac{m}{2} \rceil, which is \lfloor \frac{n + 1}{2} \rfloor times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor times \lfloor \frac{m + 1}{2} \rfloor.
The time complexity is O(1), and the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Approach 4: Mathematics (Optimized)
The result obtained from Solution 1 is \lfloor \frac{n + 1}{2} \rfloor times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor times \lfloor \frac{m + 1}{2} \rfloor.
If both n and m are odd, then the result is \frac{n + 1}{2} times \frac{m - 1}{2} + \frac{n - 1}{2} times \frac{m + 1}{2}, which is \frac{n times m - 1}{2}.
If both n and m are even, then the result is \frac{n}{2} times \frac{m}{2} + \frac{n}{2} times \frac{m}{2}, which is \frac{n times m}{2}.
If n is odd and m is even, then the result is \frac{n + 1}{2} times \frac{m}{2} + \frac{n - 1}{2} times \frac{m}{2}, which is \frac{n times m}{2}.
If n is even and m is odd, then the result is \frac{n}{2} times \frac{m - 1}{2} + \frac{n}{2} times \frac{m + 1}{2}, which is \frac{n times m}{2}.
The above four cases can be combined into \lfloor \frac{n times m}{2} \rfloor.
The time complexity is O(1), and the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using a Stack to Manage State | Time Complexity: O(1) for both push and pop operations. |
| Approach 2: Using Recursion to Simplify State Management | Time Complexity: O(n) where n is the value passed to the function. |
| Mathematics | — |
| Mathematics (Optimized) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n * m) | O(1) | Useful for understanding the rule and verifying logic with small inputs |
| Stack-Based State Tracking | O(n + m) | O(n) | When demonstrating iterative state management with explicit structures |
| Recursive Counting | O(n) | O(n) | When practicing recursion for sequential state evaluation |
| Mathematical Parity Counting | O(1) | O(1) | Best solution for large constraints and typical interview expectation |
Video Solution
Alice and Bob Playing Flower Game | Simple Math | Leetcode 3021 | codestorywithMIK • codestorywithMIK • 6,262 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Alice and Bob Playing Flower Game easy or hard?
Alice and Bob Playing Flower Game Python/Java solution
How to solve Alice and Bob Playing Flower Game in O(1)?
What is the best approach for Alice and Bob Playing Flower Game?
Is Alice and Bob Playing Flower Game asked at Google/Amazon/Meta?
What data structure is used in Alice and Bob Playing Flower Game?
What is the time complexity of Alice and Bob Playing Flower Game?
Ready to solve this problem?
Practice Alice and Bob Playing Flower Game with our built-in code editor and test cases.
Practice on FleetCode