LeetCode Problem 3021

Difficulty: 🟡 Medium
Topics: Math

Solution

LeetCode 3021 - Alice and Bob Playing Flower Game

Problem Understanding

The game consists of two flower lanes containing x and y flowers respectively. Alice moves first, and on every turn a player removes exactly one flower from either lane.

A very important observation is that the players do not have any meaningful strategic choice. Regardless of which lane a flower is removed from, every move always removes exactly one flower from the total number of flowers remaining.

Let:

$$T = x + y$$

be the total number of flowers.

Since exactly one flower disappears per turn, the game will always last exactly T turns. The winner is the player who makes the final move, because the rules state that if both lanes become empty at the end of a turn, the current player wins immediately.

Therefore, the entire game reduces to determining who makes the T-th move.

Since Alice moves first:

• Alice makes moves 1, 3, 5, ...
• Bob makes moves 2, 4, 6, ...

Therefore:

• If T is odd, Alice makes the last move and wins.
• If T is even, Bob makes the last move and wins.

The problem asks us to count how many pairs (x, y) satisfy:

• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• x + y is odd

because those are exactly the positions where Alice wins.

Understanding the Constraints

The constraints are:

• 1 ≤ n, m ≤ 100000

There can be up to:

$$100000 \times 100000 = 10^{10}$$

possible pairs.

This is far too many to enumerate directly, so any solution that checks every pair individually is impossible within time limits.

We need a mathematical counting approach.

Important Edge Cases

The smallest possible input is (1,1). The only pair is (1,1), whose sum is 2, so Alice never wins.

Cases where one dimension is 1 are useful because they make it easy to verify parity counting manually.

Large values such as (100000,100000) require an efficient formula because brute force would require checking ten billion pairs.

The problem guarantees all inputs are positive integers, so we never need to handle zero or negative flower counts.

Approaches

Brute Force

The most straightforward solution is to generate every possible pair (x, y).

For each pair:

1. Compute x + y.
2. Check whether the sum is odd.
3. If it is odd, increment the answer.

This works because we have already established that Alice wins exactly when x + y is odd.

However, there are n × m possible pairs. With n and m as large as 100000, this could require checking up to 10^10 combinations, which is far too slow.

Key Insight

A sum is odd if and only if one number is odd and the other is even.

Therefore Alice wins when:

• x is odd and y is even, or
• x is even and y is odd.

Instead of examining every pair, we can count:

• how many odd values exist in [1, n]
• how many even values exist in [1, n]
• how many odd values exist in [1, m]
• how many even values exist in [1, m]

Then:

$$\text{answer} = (\text{oddX} \times \text{evenY}) + (\text{evenX} \times \text{oddY})$$

This directly counts all winning pairs.

Since these counts can be computed with simple arithmetic, the entire solution runs in constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nm)	O(1)	Checks every possible pair individually
Optimal	O(1)	O(1)	Counts odd-even parity combinations mathematically

Algorithm Walkthrough

1. Compute the number of odd values between 1 and n.

Since odd numbers alternate with even numbers:

$$\text{oddX} = \frac{n + 1}{2}$$

using integer division. 2. Compute the number of even values between 1 and n.

$$\text{evenX} = n - \text{oddX}$$ 3. Compute the number of odd values between 1 and m.

$$\text{oddY} = \frac{m + 1}{2}$$ 4. Compute the number of even values between 1 and m.

$$\text{evenY} = m - \text{oddY}$$ 5. Count pairs where x is odd and y is even.

$$\text{oddX} \times \text{evenY}$$ 6. Count pairs where x is even and y is odd.

$$\text{evenX} \times \text{oddY}$$ 7. Add the two counts and return the result.

Why it Works

Alice wins exactly when the total number of flowers is odd. A sum is odd precisely when one operand is odd and the other is even. Every winning pair belongs to exactly one of the two categories:

• odd x, even y
• even x, odd y

The algorithm counts both categories independently and adds them together. Since the categories are disjoint and cover all odd sums, the resulting count is exactly the number of winning pairs.

Python Solution

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        odd_x = (n + 1) // 2
        even_x = n - odd_x

        odd_y = (m + 1) // 2
        even_y = m - odd_y

        return odd_x * even_y + even_x * odd_y

The implementation first computes how many odd and even values exist in each range. Integer division makes this calculation constant time.

After obtaining the parity counts, the code computes the number of odd-even pairings and the number of even-odd pairings. Their sum is returned as the final answer.

No loops, recursion, or additional data structures are needed.

Go Solution

func flowerGame(n int, m int) int64 {
	oddX := (n + 1) / 2
	evenX := n - oddX

	oddY := (m + 1) / 2
	evenY := m - oddY

	return int64(oddX*evenY + evenX*oddY)
}

The Go implementation follows exactly the same mathematical formula as the Python version.

The return type is int64, matching the required function signature. Although the maximum answer is at most 100000 × 100000 = 10^10, which exceeds a 32-bit integer range, it safely fits inside int64.

Worked Examples

Example 1

Input

n = 3, m = 2

Possible values:

• x ∈ {1,2,3}
• y ∈ {1,2}

Parity counts:

Variable	Value
oddX	2
evenX	1
oddY	1
evenY	1

Winning pairs:

x parity	y parity	Count
Odd	Even	2 × 1 = 2
Even	Odd	1 × 1 = 1

Total:

Calculation	Result
2 + 1	3

Answer:

3

The winning pairs are:

(1,2), (2,1), (3,2)

Example 2

Input

n = 1, m = 1

Parity counts:

Variable	Value
oddX	1
evenX	0
oddY	1
evenY	0

Winning pair count:

Calculation	Result
1 × 0 + 0 × 1	0

Answer:

0

The only pair is (1,1), whose sum is even, so Bob wins.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of arithmetic operations are performed
Space	O(1)	No additional data structures are allocated

The solution uses only a handful of integer variables and performs constant-time arithmetic. Its performance is independent of the sizes of n and m.

Test Cases

sol = Solution()

assert sol.flowerGame(3, 2) == 3      # provided example
assert sol.flowerGame(1, 1) == 0      # smallest input

assert sol.flowerGame(2, 2) == 2      # balanced small case
assert sol.flowerGame(1, 2) == 1      # single odd x value
assert sol.flowerGame(2, 1) == 1      # single odd y value

assert sol.flowerGame(3, 3) == 4      # symmetric odd ranges
assert sol.flowerGame(4, 4) == 8      # symmetric even ranges

assert sol.flowerGame(5, 2) == 5      # odd-sized first range
assert sol.flowerGame(2, 5) == 5      # odd-sized second range

assert sol.flowerGame(100000, 100000) == 5000000000  # maximum constraints
assert sol.flowerGame(99999, 100000) == 5000000000   # mixed parity limits

Test Summary

Test	Why
(3,2)	Verifies the first example
(1,1)	Verifies the second example
(2,2)	Small even ranges
(1,2)	Single possible x value
(2,1)	Single possible y value
(3,3)	Symmetric odd-sized ranges
(4,4)	Symmetric even-sized ranges
(5,2)	Uneven dimensions
(2,5)	Uneven dimensions in reverse order
(100000,100000)	Maximum constraint stress test
(99999,100000)	Large mixed parity case

Edge Cases

Minimum Input Size

When n = 1 and m = 1, there is only one pair, (1,1). Its sum is 2, which is even, so Alice cannot win. A solution that incorrectly assumes at least one winning configuration would fail here. The parity-counting formula correctly produces zero.

One Range Contains Only One Value

Inputs such as (1,100000) or (100000,1) are easy places for off-by-one mistakes when counting odd and even numbers. The implementation explicitly computes odd and even counts using arithmetic formulas, so these cases are handled correctly without special logic.

Maximum Constraints

For (100000,100000), there are ten billion possible pairs. Any brute-force enumeration would be infeasible. The mathematical solution performs only a few arithmetic operations and returns the answer immediately. The Go implementation returns an int64, ensuring the result fits safely within the available integer range.