Jonas Notes

Alice and Bob Playing Flower Game

2 min read

Problem

Alice and Bob Playing Flower Game

Approach

My first thought was that as long as the sum of the pairs is odd, then it is a valid pair. And it just has to fit the requirements which is that x ⇐ n and y ⇐ m and x >= 1 and y >= 1. I later found out that to get an odd pair, we need one even and one odd number, which fits with what the hint said. But how do we code out such a solution?

My initial plan was to do a pretty simple code which is to do dfs, starting from n,m we slowly decrement it and try every pair, but we also need to store the visited pairs. This would be O(nm) for both space and time. Met with memory limit exceeded.

Well it turns out that the solution was much easier than I thought. So since we only want the odd pairs, we will realise that out of all the pairs, half of them are either odd and the other half will be even. So all we have to do is find all the pairs and divide them by 2. Sounds dumb… I don’t think this question will ever come out during interviews.

Complexity

  • Time: O(1)
  • Space: O(1)

Code

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        return (n*m) // 2

Backlinks