# Alice and Bob Playing Flower Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/alice-and-bob-playing-flower-game)
Canonical: https://scaleengineer.com/dsa/problems/alice-and-bob-playing-flower-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
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:

1. Alice takes the first turn.
2. In each turn, a player must choose either the clockwise or anti-clockwise direction and pick one flower from that side.
3. 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 `x` in the clockwise direction must be in the range `[1,n]`.
* The number of flowers `y` in 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`

# Approaches
## Brute-Force Iteration
This approach directly translates the problem statement into code. We check every possible pair `(x, y)` within the given ranges `[1, n]` and `[1, m]`. For each pair, we determine the winner of the game and count the pairs where Alice wins.
**Time:** O(n * m). The nested loops run `n` and `m` times, respectively, leading to `n * m` checks. For constraints like `n, m <= 10^5`, this is too slow. · **Space:** O(1). We only use a constant amount of extra space for the counter and loop variables.
**Pros:** Simple to understand and implement.; Directly follows the problem's logic without requiring complex insights.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints (`n, m <= 10^5`).
### Explanation
The core of the game is that it lasts for `x + y` turns. Alice takes the 1st, 3rd, 5th, ... turns, while Bob takes the 2nd, 4th, 6th, ... turns. The player who takes the last flower wins. This means if the total number of turns, `x + y`, is odd, Alice will take the last turn and win. If `x + y` is even, Bob will take the last turn and win.

The algorithm iterates through all possible values of `x` from 1 to `n` and for each `x`, it iterates through all possible values of `y` from 1 to `m`. Inside the inner loop, it calculates the sum `x + y` and checks if it's odd. If `x + y` is odd, it means Alice wins for this pair `(x, y)`, so we increment a counter. After checking all `n * m` pairs, the counter will hold the total number of pairs where Alice wins.

```java
class Solution {
    public long flowerGame(int n, int m) {
        long count = 0;
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= m; y++) {
                // Alice wins if the total number of flowers (turns) is odd.
                if ((x + y) % 2 != 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Create a loop for `x` from 1 to `n`.
- Inside this loop, create another loop for `y` from 1 to `m`.
- In the inner loop, check if the sum `x + y` is odd. The condition `(x + y) % 2 != 0` can be used for this.
- If the condition is true, it means Alice wins for the pair `(x, y)`, so increment the `count`.
- After both loops complete, the `count` will hold the total number of pairs for which Alice wins. Return `count`.

## Optimized Iteration by Parity
This approach improves upon the brute-force method by avoiding the inner loop. Instead of checking each `y` for a given `x`, we can directly calculate how many valid `y` values exist based on parity.
**Time:** O(n) or O(m). The complexity is linear with respect to the dimension we choose to iterate over. This is a significant improvement and is efficient enough. · **Space:** O(1). We use a constant amount of extra space for counters and variables.
**Pros:** Much more efficient than the brute-force approach.; Passes the time limits for the given constraints.; Still relatively easy to understand.
**Cons:** While efficient enough for the given constraints, it is not the most optimal solution as a constant time approach exists.
### Explanation
We still iterate through each possible value of `x` from 1 to `n`. For each `x`, we analyze its parity (whether it's odd or even). Based on the game's winning condition (`x + y` must be odd), if `x` is odd, `y` must be even. If `x` is even, `y` must be odd. So, for each `x`, we count the number of `y` values in the range `[1, m]` that have the required opposite parity and add this to our total. The number of even integers in `[1, m]` is `m / 2`, and the number of odd integers is `(m + 1) / 2`.

```java
class Solution {
    public long flowerGame(int n, int m) {
        long count = 0;
        long evenYCount = (long)m / 2;
        long oddYCount = (long)(m + 1) / 2;
        
        for (int x = 1; x <= n; x++) {
            if (x % 2 != 0) { // x is odd, y must be even
                count += evenYCount;
            } else { // x is even, y must be odd
                count += oddYCount;
            }
        }
        return count;
    }
}
```
### Algorithm
- Pre-calculate the number of even `y`'s (`evenY = m / 2`) and odd `y`'s (`oddY = (m + 1) / 2`) in the range `[1, m]`.
- Initialize a total count `count` to 0.
- Loop `x` from 1 to `n`.
- If `x` is odd (`x % 2 != 0`), it means `y` must be even for the sum to be odd. Add the pre-calculated `evenY` to `count`.
- If `x` is even (`x % 2 == 0`), it means `y` must be odd. Add the pre-calculated `oddY` to `count`.
- After the loop finishes, return `count`.

## Constant Time Mathematical Solution
This is the most efficient approach. It solves the problem by deriving a direct mathematical formula based on the parity of `x` and `y`, eliminating the need for any loops.
**Time:** O(1). The solution involves a fixed number of arithmetic operations, making it independent of the input size. · **Space:** O(1). Only a few variables are used for the calculation, requiring constant extra space.
**Pros:** Optimal solution with constant time complexity.; Extremely efficient and scalable, regardless of the size of `n` and `m`.
**Cons:** Requires a mathematical insight into the problem structure, which might be less intuitive than iterative solutions.
### Explanation
The problem boils down to a combinatorial task: counting pairs `(x, y)` where `1 <= x <= n`, `1 <= y <= m`, and `x + y` is odd. The sum `x + y` is odd if and only if `x` and `y` have different parities. This gives us two disjoint cases to count:

1.  **`x` is odd and `y` is even:** The number of ways to choose an odd `x` from `[1, n]` is `(n + 1) / 2`. The number of ways to choose an even `y` from `[1, m]` is `m / 2`. The total pairs for this case is `((n + 1) / 2) * (m / 2)`.
2.  **`x` is even and `y` is odd:** The number of ways to choose an even `x` from `[1, n]` is `n / 2`. The number of ways to choose an odd `y` from `[1, m]` is `(m + 1) / 2`. The total pairs for this case is `(n / 2) * ((m + 1) / 2)`.

The final answer is the sum of the counts from both cases. Since the result can be large, we should use `long` for calculations to prevent integer overflow.

```java
class Solution {
    public long flowerGame(int n, int m) {
        // Alice wins if x + y is odd.
        // This happens if (x is odd and y is even) OR (x is even and y is odd).
        
        // Count odd and even numbers in the range [1, n]
        long oddX = (long)(n + 1) / 2;
        long evenX = (long)n / 2;
        
        // Count odd and even numbers in the range [1, m]
        long oddY = (long)(m + 1) / 2;
        long evenY = (long)m / 2;
        
        // Total pairs = (number of odd x * number of even y) + (number of even x * number of odd y)
        return oddX * evenY + evenX * oddY;
    }
}
```
### Algorithm
- Identify that Alice wins if and only if `x + y` is odd.
- This occurs in two mutually exclusive cases: (1) `x` is odd and `y` is even, or (2) `x` is even and `y` is odd.
- Calculate the number of odd and even integers in the range `[1, n]`:
  - `oddX = (n + 1) / 2`
  - `evenX = n / 2`
- Calculate the number of odd and even integers in the range `[1, m]`:
  - `oddY = (m + 1) / 2`
  - `evenY = m / 2`
- The total number of winning pairs is the sum of pairs from the two cases: `(oddX * evenY) + (evenX * oddY)`.
- Return this result. Use `long` for calculations to prevent potential integer overflow.

# Solutions
### Java

```java
class Solution {
public
  long flowerGame(int n, int m) {
    long a1 = (n + 1) / 2;
    long b1 = (m + 1) / 2;
    long a2 = n / 2;
    long b2 = m / 2;
    return a1 * b2 + a2 * b1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long flowerGame(int n, int m) {
    long long a1 = (n + 1) / 2;
    long long b1 = (m + 1) / 2;
    long long a2 = n / 2;
    long long b2 = m / 2;
    return a1 * b2 + a2 * b1;
  }
};

```

### Python

```python
class Solution:
    def flowerGame(self, n: int, m: int) -> int: a1 = (n + 1) // 2 b1 = (m + 1) // 2 a2 = n // 2 b2 = m // 2 return a1 * b2 + a2 * b1

```