Divisor Game — LeetCode #1025 (Easy)
Tags: Math, Dynamic Programming, Brainteaser, Game Theory
Related patterns: Game Theory, Dynamic Programming
Brute Force approach
Time complexity: O(n²). Space complexity: O(1).
In the brute force approach, we simulate every possible move Alice and Bob can make. We recursively explore all valid moves until we reach a base case where a player cannot make a move, determining the winner based on that.
The time complexity is O(n²) because for each number n, we may check up to n possible moves, leading to a quadratic growth in the number of recursive calls.
- Step 1: Create a recursive function that takes the current number n and a boolean indicating if it's Alice's turn.
- Step 2: If n is 0, return false (the player who cannot make a move loses).
- Step 3: For each possible move x (where 0 < x < n and n % x == 0), recursively call the function for n - x, toggling the turn.
- Step 4: If any recursive call returns false, it means the opponent cannot win, so return true (the current player wins).
- Step 5: If all moves lead to a winning position for the opponent, return false.
1. n = 2, Alice's turn. Possible moves: [1].
2. Alice chooses 1, now n = 1, Bob's turn.
3. n = 1, Bob has no valid moves (0 < x < 1).
4. Bob loses, Alice wins.
Optimal Solution approach
Time complexity: O(1). Space complexity: O(1).
The optimal solution leverages the observation that if n is even, Alice can always make it odd for Bob, leading to a win. Conversely, if n is odd, Bob can always return it to even for Alice, leading to his win. Thus, the outcome depends solely on the parity of n.
The time complexity is O(1) because we only perform a single modulus operation, and space complexity is also O(1) as we use no additional space.
- Step 1: Check if n is even.
- Step 2: If n is even, return true (Alice wins).
- Step 3: If n is odd, return false (Bob wins).
1. n = 2, check if even: 2 % 2 == 0.
2. Return true, Alice wins.
Key Insights
- Alice wins if n is even; Bob wins if n is odd.
- The game can be reduced to a simple parity check.
Common Mistakes
- Not recognizing the importance of even vs. odd in determining the winner.
- Overcomplicating the recursive approach instead of simplifying to a parity check.
Interview Tips
- Always start by analyzing the problem for patterns or properties (like parity).
- Think about edge cases and how they affect the game.
- Be prepared to explain your reasoning clearly, especially if you simplify the solution.
