Scale Engineer

Alice and Bob Playing Flower Game

Med
#2689Time: 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.1 company
Patterns
Math
Companies
Rubrik

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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).

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem