LeetCode Entry
3021. Alice and Bob Playing Flower Game
Pairs x=1..n y=1..m for Alice to win in take from (x+y) game
3021. Alice and Bob Playing Flower Game medium blog post substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1096
Problem TLDR
Pairs x=1..n * y=1..m for Alice to win in take from (x+y) game #medium
Intuition
Count odd x+y. It is sum of first odd+second even or reversed.
The interesting math fact from others (can be proved by considering 4 cases: even-even, even-odd,odd-even, odd-odd):
n/2 * (m+1)/2 + m/2 * (n+1)/2 == n*m/2
Approach
- try to write O(1)
Complexity
-
Time complexity: \(O(1)\)
-
Space complexity: \(O(1)\)
Code
// 0ms
fun flowerGame(n: Int, m: Int) =
1L * (n/2) * ((m+1)/2) + 1L * ((n+1)/2) * (m/2)
// 11ms
fun flowerGame(n: Int, m: Int): Long {
val ne = (2..n).count { it % 2 < 1 }
val me = (2..m).count { it % 2 < 1 }
return 1L * (n-ne) * me + 1L * ne * (m-me)
}
// 0ms
pub fn flower_game(n: i32, m: i32) -> i64 {
n as i64 * m as i64 / 2
}
// 0ms
long long flowerGame(int n, int m) {
return 1LL * n * m / 2;
}
// 0ms
flowerGame = lambda _,n,m: n*m//2