1025. Divisor Game

📝 Problem Details

• Title: 1025. Divisor Game
• Link: https://leetcode.com/problems/divisor-game/
• Difficulty: Easy
• Tags/Categories: Math Dynamic-Programming

💭What Were My Initial Thoughts?

rules:
- alice and bob take turns picking a divisor x of n (where x is between 1 and n non-inclusive)
- the number n is updated to n - x
- if a player can't make a move, they lose
- alice always goes first

🤔What Did I Struggle With?

~

💡 Explanation of Solution

OBSERVATION: alice can always win if n is even, and will always lose if n is odd
- **Base Cases**:
    - n=1n = 1n=1: Alice loses because no moves are possible (losing state).
    - n=2n = 2n=2: Alice wins because she can make n=1n = 1n=1 for Bob (winning state).

- **Inductive Step for n > 2:
    - If nnn is **even**, Alice can always make nnn **odd** for Bob's turn.
    - If nnn is **odd**, Bob can always make nnn **even** for Alice's turn.
    - By repeating this process, nnn will eventually reduce to either:
        - n=1n = 1n=1, where Alice loses if it's her turn (Bob wins).
        - n=2n = 2n=2, where Alice wins if it's her turn.

- **Key Insight**:
    - The parity of n (even or odd) determines the outcome:
        - If n is **even** at the start, Alice has a strategy to always make Bob face odd n, ensuring her eventual win.
        - If n is **odd** at the start, Bob has a strategy to always make Alice face even n, ensuring her eventual loss.

- **Conclusion**:
    - For any n>2, the game reduces to one of the base cases (n=1 or n=2).
    - The outcome of the game depends solely on the parity of nnn at the start:
        - Alice wins if nnn is even.
        - Alice loses if nnn is odd.

⌛ Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
	bool divisorGame(int n) {
		return n%2 == 0;
	}
}