Alice and Bob Playing Flower Game solution and explanation
Google
9 more videos on this problem
Alice and Bob Playing Flower Game | Simple Math | Leetcode 3021 | codestorywithMIKcodestorywithMIK · 13:10 · 6K views
Alice and Bob Playing Flower Game | Leetcode 3021Techdose · 13:44 · 2K views
3021. Alice and Bob Playing Flower Game | Fancy Math++ | Easy Game TheoryAryan Mittal · 20:48 · 2K views
3021. Alice and Bob Playing Flower Game | Leetcode Daily - PythonLeetcode Daily · 4:35 · 492 views
3021. Alice and Bob Playing Flower Game | Harder Follow-up | Weekly Leetcode 382codingMohan · 14:36 · 485 views
Leetcode | 3021. Alice and Bob Playing Flower Game | Medium | Java SolutionDeveloper Docs · 5:19 · 458 views
3021. Alice and Bob Playing Flower Game (Leetcode Medium)Programming Live with Larry · 8:19 · 405 views
Leetcode 3021 🔥 Alice and Bob Playing Flower Game | Intuition + Optimal Solution Study Placement · 5:49 · 395 views
Leetcode 3021. Alice and Bob Playing Flower Game | Brute Force → Math Simple | Python SolutionStatLearn Tech · 16:10 · 173 views
LeetCode 3021 - Alice and Bob Playing Flower Game - PythonAlpha-Code · 10:14 · 140 views
The 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:
- 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.
stack = []
# Push elements
stack.append(10)
stack.append(20)
# Pop elements
print('Popped:', stack.pop())
print('Popped:', stack.pop())import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
System.out.println("Popped: " + stack.pop());
System.out.println("Popped: " + stack.pop());
}
}#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
s.push(10);
s.push(20);
std::cout << "Popped: " << s.top() << std::endl;
s.pop();
std::cout << "Popped: " << s.top() << std::endl;
s.pop();
return 0;
}let stack = [];
// Push elements
stack.push(10);
stack.push(20);
// Pop elements
console.log('Popped:', stack.pop());
console.log('Popped:', stack.pop());#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
int stack[MAXSIZE];
int top = -1;
void push(int value) {
if (top < MAXSIZE - 1) {
stack[++top] = value;
}
}
int pop() {
if (top >= 0) {
return stack[top--];
}
return -1; // Indicate an error
}
int main() {
// Example usage:
push(10);
push(20);
printf("Popped: %d\n", pop());
printf("Popped: %d\n", pop());
return 0;
}using System;
using System.Collections.Generic;
class Program {
static void Main() {
Stack<int> stack = new Stack<int>();
stack.Push(10);
stack.Push(20);
Console.WriteLine("Popped: " + stack.Pop());
Console.WriteLine("Popped: " + stack.Pop());
}
}This Python code uses a list as a stack. The list's append method is used for pushing, and pop is used for popping elements. Python's dynamic arrays make this approach efficient and easy to implement.
Time Complexity: O(1) for append and pop.
Space Complexity: O(n) where n is the number of elements in the stack.
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.
def recursive_function(n):
if n <= 0:
return
print(n)
recursive_function(n - 1)
recursive_function(5)public class Main {
static void recursiveFunction(int n) {
if (n <= 0) return;
System.out.println(n);
recursiveFunction(n - 1);
}
public static void main(String[] args) {
recursiveFunction(5);
}
}#include <iostream>
void recursiveFunction(int n) {
if (n <= 0) return;
std::cout << n << std::endl;
recursiveFunction(n - 1);
}
int main() {
recursiveFunction(5);
return 0;
}function recursiveFunction(n) {
if (n <= 0) return;
console.log(n);
recursiveFunction(n - 1);
}
recursiveFunction(5);#include <stdio.h>
void recursiveFunction(int n) {
if (n <= 0) return;
printf("%d\n", n);
recursiveFunction(n - 1);
}
int main() {
recursiveFunction(5);
return 0;
}using System;
class Program {
static void RecursiveFunction(int n) {
if (n <= 0) return;
Console.WriteLine(n);
RecursiveFunction(n - 1);
}
static void Main() {
RecursiveFunction(5);
}
}This Python function uses recursion to print numbers from n down to 1. Python's function call stack automatically manages state during recursion.
Time Complexity: O(n) where n is the initial input.
Space Complexity: O(n) due to the depth of recursive calls.
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).
function flowerGame(n: number, m: number): number {
const [a1, b1] = [(n + 1) >> 1, (m + 1) >> 1];
const [a2, b2] = [n >> 1, m >> 1];
return a1 * b2 + a2 * b1;
}func flowerGame(n int, m int) int64 {
a1, b1 := (n+1)/2, (m+1)/2
a2, b2 := n/2, m/2
return int64(a1*b2 + a2*b1)
}impl Solution {
pub fn flower_game(n: i32, m: i32) -> i64 {
let a1 = ((n + 1) / 2) as i64;
let b1 = ((m + 1) / 2) as i64;
let a2 = (n / 2) as i64;
let b2 = (m / 2) as i64;
a1 * b2 + a2 * b1
}
}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).
function flowerGame(n: number, m: number): number {
return Number(((BigInt(n) * BigInt(m)) / 2n) | 0n);
}func flowerGame(n int, m int) int64 {
return int64((n * m) / 2)
}impl Solution {
pub fn flower_game(n: i32, m: i32) -> i64 {
(n as i64 * m as i64) / 2
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using a Stack to Manage State | Time Complexity: O(1) for append and pop. |
| Approach 2: Using Recursion to Simplify State Management | Time Complexity: O(n) where n is the initial input. |
| Mathematics | – |
| Mathematics (Optimized) | – |
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 |
Frequently asked questions
Is Alice and Bob Playing Flower Game easy or hard?
The problem is rated Medium on LeetCode with about a 60% acceptance rate. The implementation is simple once you recognize the parity pattern, but many candidates initially attempt brute force enumeration before spotting the mathematical shortcut.
Alice and Bob Playing Flower Game Python/Java solution
Most implementations compute odd and even counts using integer division and then apply the formula odd_x * even_y + even_x * odd_y. This logic translates directly to Python, Java, C++, JavaScript, and other languages because it uses only basic arithmetic operations.
How to solve Alice and Bob Playing Flower Game in O(1)?
Compute the number of odd and even integers in each range. In 1..n, odd = (n + 1) / 2 and even = n / 2. In 1..m, odd = (m + 1) / 2 and even = m / 2. The number of winning pairs is odd_x * even_y + even_x * odd_y, which can be calculated directly without loops.
What is the best approach for Alice and Bob Playing Flower Game?
The optimal approach uses mathematical parity counting. Alice wins when the sum x + y is odd, which only happens when one number is odd and the other is even. Count odd and even numbers in both ranges and compute odd_x * even_y + even_x * odd_y. This runs in O(1) time and O(1) space.
Is Alice and Bob Playing Flower Game asked at Google/Amazon/Meta?
Parity counting and combinatorics problems similar to this appear frequently in coding interviews at companies like Amazon, Google, and Meta. The exact problem may vary, but recognizing patterns involving odd/even properties and counting valid combinations is a common interview skill.
What data structure is used in Alice and Bob Playing Flower Game?
The optimal solution does not require any complex data structure. It relies purely on mathematical counting of odd and even numbers. Alternative educational implementations may use recursion or a stack to simulate state traversal, but they are unnecessary for the final optimized solution.
What is the time complexity of Alice and Bob Playing Flower Game?
The optimal solution runs in O(1) time because it only counts odd and even numbers in the ranges 1..n and 1..m and applies a formula. A brute force solution that checks every pair takes O(n * m) time.