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.

Examples

Example 1:

1
2
3

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:

1
2
3

Input: n = 1, m = 1
Output: 0
Explanation: No pairs satisfy the conditions described in the statement.

Constraints:

  • 1 <= n, m <= 10^5

Solution

Method 1 - Naive

To determine the number of pairs (x, y) that satisfy the conditions:

  1. Alice’s First Choice: Alice wins the game if she can ensure that the sum of flowers x + y is odd. An odd total ensures that Bob gets fewer turns than Alice and eventually Alice makes the last move, leading to her victory.

  2. Range Constraints: Both x and y are restricted to specific ranges: 1 ≤ x ≤ n and 1 ≤ y ≤ m.

  3. Iterative Checking:

    • Loop through all possible values of x within [1, n].
    • For each value of x, loop through all possible values of y within [1, m].
    • For every pair (x, y), check if the sum x + y is odd.
    • Count all such valid pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public long flowerGame(int n, int m) {
        long ans = 0;  // Use long since the result may grow large for higher values of n and m
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= m; y++) {
                if ((x + y) % 2 == 1) {  // Check if the sum of x and y is odd
                    ans++;
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def alice_wins(self, n: int, m: int) -> int:
        ans: int = 0
        for x in range(1, n + 1):
            for y in range(1, m + 1):
                if (x + y) % 2 == 1:
                    ans += 1
        return ans

Complexity

  • ⏰ Time complexity: O(n * m) (Two nested loops to iterate through all possible values for x and y).
  • 🧺 Space complexity: - O(1) (No extra space used apart from a variable to store the count).

Method 2 - Using Maths

To improve the performance and avoid TLE (Time Limit Exceeded), we need to optimise the brute-force approach with mathematical insights instead of iterating through all pairs (x, y).

From the problem:

  • Alice wins if the sum x + y is odd.
  • Odd or even totals alternate between pairs (x, y), so we can directly count how many such pairs satisfy the condition:
    • Total pairs (x, y) = n * m.
    • Half of these pairs have odd sums and half have even sums, as odd and even sums alternate evenly in a grid.

Key Insight:

  • Count of odd sums:
    • Compute the count of odd x values and odd y values.
    • Compute the count of even x values and even y values.
    • Pairs with (odd x, even y) or (even x, odd y) give odd sums.

Steps:

  1. Count odd and even values in the ranges [1, n] and [1, m].
    • Odd numbers in [1, n] → (n + 1) / 2.
    • Even numbers in [1, n] → n / 2.
    • Similarly for [1, m].
  2. Compute odd-sum pairs:
    • odd_x * even_y + even_x * odd_y.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public long flowerGame(int n, int m) {
        // Calculate counts of odd and even values in both ranges
        long oddX = (n + 1) / 2;    // Odd numbers in the range [1, n]
        long evenX = n / 2;         // Even numbers in the range [1, n]
        long oddY = (m + 1) / 2;    // Odd numbers in the range [1, m]
        long evenY = m / 2;         // Even numbers in the range [1, m]

        // Compute number of pairs where the sum is odd
        long result = oddX * evenY + evenX * oddY;

        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def flower_game(self, n: int, m: int) -> int:
        # Calculate counts of odd and even values in both ranges
        odd_x: int = (n + 1) // 2  # Odd numbers in the range [1, n]
        even_x: int = n // 2       # Even numbers in the range [1, n]
        odd_y: int = (m + 1) // 2  # Odd numbers in the range [1, m]
        even_y: int = m // 2       # Even numbers in the range [1, m]

        # Compute number of pairs where the sum is odd
        result: int = odd_x * even_y + even_x * odd_y

        return result

Complexity

  • ⏰ Time complexity: O(1) — Direct computations using arithmetic operations only.
  • 🧺 Space complexity: O(1) — Uses only constant space for variables.