207. Divisor Game

🔗 LeetCode Problem: 1025. Divisor Game
📊 Difficulty: Easy
🏷️ Topics: Dynamic Programming, Math, Game Theory, Brainteaser, 1D DP

Problem Statement

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < n and n % x == 0.
• Replacing the number n on the chalkboard with n - x.

Also, if a player cannot make a move, they lose the game.

Return true if and only if Alice wins the game, assuming both players play optimally.

Example 1:

Input: n = 2
Output: true
Explanation: 
  Alice chooses 1, n becomes 1.
  Bob cannot make a move, so Alice wins.

Example 2:

Input: n = 3
Output: false
Explanation: 
  Alice chooses 1, n becomes 2.
  Bob chooses 1, n becomes 1.
  Alice cannot make a move, so Bob wins.

Example 3:

Input: n = 4
Output: true
Explanation:
  Alice chooses 1, n becomes 3.
  Bob chooses 1, n becomes 2.
  Alice chooses 1, n becomes 1.
  Bob cannot make a move, so Alice wins.

Constraints: - 1 <= n <= 1000

---

🌳 Visual Understanding - The Game Theory Problem

The Problem We're Solving:

Two players: Alice (A) and Bob (B)
Turn order: Alice goes FIRST

Board: Number n on chalkboard

Each turn:
  1. Choose x where: 0 < x < n AND n % x == 0 (x divides n)
  2. Replace n with (n - x)
  3. If cannot move → LOSE!

Question: Does Alice win if both play optimally? 🤔

Understanding Valid Moves:

For n = 6:
  Divisors of 6: 1, 2, 3, 6
  Valid choices for x: 1, 2, 3 (exclude 6 itself, must be < n)

  Possible moves:
    - Choose x=1 → n becomes 6-1=5
    - Choose x=2 → n becomes 6-2=4
    - Choose x=3 → n becomes 6-3=3

For n = 5:
  Divisors of 5: 1, 5
  Valid choices for x: 1 (exclude 5 itself)

  Possible moves:
    - Choose x=1 → n becomes 5-1=4

For n = 1:
  Divisors of 1: 1
  Valid choices for x: NONE (can't choose 1 because x < n, and 1 is not < 1)

  Cannot move → LOSE! ❌

Game Tree for n = 4:

                    n=4 (Alice's turn)
                     │
        ┌────────────┼────────────┐
        │                         │
     x=1│                      x=2│
        ↓                         ↓
      n=3                       n=2
   (Bob's turn)              (Bob's turn)
        │                         │
        │x=1                   x=1│
        ↓                         ↓
      n=2                       n=1
 (Alice's turn)              (Alice LOSES!)
        │
     x=1│
        ↓
      n=1
  (Bob LOSES!)

Optimal play:
  Alice chooses x=1 → n=3
  Bob chooses x=1 → n=2
  Alice chooses x=1 → n=1
  Bob cannot move → Alice WINS! ✓

Game Tree for n = 3:

           n=3 (Alice's turn)
            │
            │x=1 (only choice)
            ↓
           n=2 (Bob's turn)
            │
            │x=1 (only choice)
            ↓
           n=1 (Alice LOSES!)

Optimal play:
  Alice chooses x=1 → n=2
  Bob chooses x=1 → n=1
  Alice cannot move → Bob WINS! ❌

Pattern Observation:

Let's trace small values:

n=1: Alice cannot move → Alice LOSES (false)
n=2: Alice chooses 1 → n=1 → Bob LOSES → Alice WINS (true)
n=3: Alice chooses 1 → n=2 → Bob WINS → Alice LOSES (false)
n=4: Alice chooses 1 → n=3 → Bob LOSES → Alice WINS (true)
n=5: Alice chooses 1 → n=4 → Bob WINS → Alice LOSES (false)
n=6: Alice can choose 1,2,3 → best is choose 1 → n=5 → Bob LOSES → Alice WINS (true)

Pattern:
  n=1: false
  n=2: true
  n=3: false
  n=4: true
  n=5: false
  n=6: true

OBSERVATION: Alice wins if n is EVEN! 🎯
              Alice loses if n is ODD! 

Why? We'll discover through DP! 🔍

---

🧠 The AHA Moment - Why Dynamic Programming?

Key Observation:

For current player at position n:
  - They WIN if they can make a move that puts opponent in LOSING position
  - They LOSE if ALL their moves put opponent in WINNING position

This is a classic GAME THEORY problem! 🎮

Recursive definition:
  canWin(n) = true if EXISTS a move x such that:
              - 0 < x < n
              - n % x == 0
              - canWin(n - x) = false (opponent loses!)

  canWin(n) = false if ALL valid moves lead to:
              - canWin(n - x) = true (opponent wins!)

Why Not Greedy?

Greedy approach: "Choose the largest divisor"

For n = 6:
  Largest divisor < 6 = 3
  Choose 3 → n becomes 3
  Opponent at n=3... do they win?

We don't know without exploring ALL possibilities!

Greedy doesn't work because:
  - The "best" move depends on what happens LATER
  - Need to think ahead: "If I do this, opponent does that..."
  - Must explore ALL possible game paths

Need DP to determine optimal play! 🎯

Why Dynamic Programming?

1. OVERLAPPING SUBPROBLEMS:
   To find canWin(6), we might check canWin(5), canWin(4), canWin(3)
   To find canWin(4), we might check canWin(3), canWin(2)

   Notice: canWin(3) needed MULTIPLE times! ⚠️

2. OPTIMAL SUBSTRUCTURE:
   Whether current player wins depends on whether opponent wins
   Solution to larger problem uses solutions to smaller ones

3. GAME THEORY:
   Classic minimax pattern:
     - I win if opponent loses
     - I lose if opponent wins for ALL my moves

These properties = Perfect for DP! 🎯

---

🔴 Approach 1: Brute Force (Recursion)

📐 Function Definition

Function Signature:

boolean divisorGame(int n)

What it represents:

Input Parameter n: - The current number on the chalkboard - Represents the game state/position - Example: n=4 means "there's a 4 on the board"

Return Value (boolean): - true = Current player (the one whose turn it is at position n) WINS - false = Current player (the one whose turn it is at position n) LOSES - Example: divisorGame(4) = true means "player starting at n=4 wins"

Purpose: - Determine if the player whose turn it is at position n will win - Assumes both players play optimally - Explores all possible moves and their outcomes

Key Understanding:

divisorGame(5) asks: "If it's my turn and n=5, do I win?"

Answer process:
  - Try all valid moves (divisors of 5)
  - For each move, check if opponent loses
  - If ANY move makes opponent lose → I win (return true)
  - If ALL moves make opponent win → I lose (return false)

Example:
  divisorGame(2) = true
  Meaning: "Player at position 2 wins"
  Why: Choose x=1 → opponent at position 1 → opponent loses

💡 Intuition

At position n, try ALL valid moves:
  - For each divisor x of n (where 0 < x < n):
    - Make move: n becomes (n - x)
    - Check if opponent LOSES from position (n - x)
    - If opponent loses → we WIN!

If ANY move makes opponent lose → we WIN
If ALL moves make opponent win → we LOSE

Base case:
  - n = 1: Cannot make any move → LOSE (return false)

Recursion explores all game possibilities!

📝 Implementation

class Solution {
    public boolean divisorGame(int n) {
        // Base case: n = 1, cannot make a move
        if (n == 1) {
            return false;  // Current player loses
        }

        // Try all possible moves
        for (int x = 1; x < n; x++) {
            // Check if x is a valid divisor
            if (n % x == 0) {
                // Make move: n becomes (n - x)
                // If opponent LOSES from (n - x), we WIN!
                if (!divisorGame(n - x)) {
                    return true;  // Found a winning move!
                }
            }
        }

        // All moves lead to opponent winning
        return false;  // We lose
    }
}

🔍 Dry Run Example: n = 4

divisorGame(4) - "Does player at position 4 win?"
├─ Try x=1: 4%1=0 ✓ valid
│  ├─ Check: !divisorGame(3) - "Does opponent lose at position 3?"
│  │  │
│  │  ├─ divisorGame(3) - "Does player at position 3 win?"
│  │  │  ├─ Try x=1: 3%1=0 ✓ valid
│  │  │  │  ├─ Check: !divisorGame(2) - "Does opponent lose at position 2?"
│  │  │  │  │  │
│  │  │  │  │  ├─ divisorGame(2) - "Does player at position 2 win?"
│  │  │  │  │  │  ├─ Try x=1: 2%1=0 ✓ valid
│  │  │  │  │  │  │  ├─ Check: !divisorGame(1)
│  │  │  │  │  │  │  │  └─ divisorGame(1) → return false (base case: cannot move)
│  │  │  │  │  │  │  ├─ !false = true
│  │  │  │  │  │  │  └─ return true (found winning move!)
│  │  │  │  │  │  │
│  │  │  │  │  │  └─ divisorGame(2) = true ✓ "Player at 2 wins"
│  │  │  │  │  │
│  │  │  │  │  ├─ !true = false
│  │  │  │  │  └─ Continue checking other moves
│  │  │  │  │
│  │  │  │  ├─ Try x=2: 3%2=1 ✗ invalid
│  │  │  │  └─ No more valid moves
│  │  │  │
│  │  │  └─ return false (all moves lost)
│  │  │     Meaning: "Player at position 3 loses"
│  │  │
│  │  ├─ divisorGame(3) = false ✓ "Player at 3 loses"
│  │  ├─ !false = true → "Opponent loses!"
│  │  └─ return true (found winning move!)
│  │
│  └─ !divisorGame(3) = !false = true
│     └─ return true immediately!
│
└─ divisorGame(4) = true ✓
   Meaning: "Player at position 4 WINS"

Result: Alice starts at position 4 → Alice WINS! ✓

Function calls and their meanings:
  divisorGame(4) = true  → "Player at 4 wins"
  divisorGame(3) = false → "Player at 3 loses"
  divisorGame(2) = true  → "Player at 2 wins"
  divisorGame(1) = false → "Player at 1 loses" (base case)

📊 Complexity Analysis

Time Complexity: O(n!)

Worse than exponential!

At each level:
  - Try up to (n-1) moves
  - Each move branches to another recursive call

For n=4: ~24 calls
For n=10: ~3,628,800 calls! 💥
Factorial explosion!

Space Complexity: O(n)

Recursion stack depth ≈ n
In worst case, go from n → n-1 → n-2 → ... → 1

Why This Fails:

❌ Factorial time - extremely slow
❌ Recalculates same subproblems many times
❌ Too slow for n=1000
✅ But shows the game theory structure clearly!

---

🟡 Approach 2: Top-Down (Memoization)

📐 Function Definition

Function Signature:

boolean canWin(int n, Boolean[] memo)

What it represents:

Input Parameter n: - The current number on the chalkboard - Represents the game state/position - Example: n=5 means "board shows 5"

Input Parameter memo: - Memoization cache (array of size n+1) - memo[i] stores the result for position i - null = not yet calculated - true = player at position i wins - false = player at position i loses

Return Value (boolean): - true = Current player at position n WINS with optimal play - false = Current player at position n LOSES with optimal play

Purpose: - Same as brute force BUT with caching - Avoid recalculating same positions - Store results in memo array for reuse

Key Understanding:

canWin(5, memo) asks: "If it's my turn at n=5, do I win?"

First time calling canWin(5, memo):
  - memo[5] = null (not calculated)
  - Calculate the answer
  - Store in memo[5]
  - Return the result

Second time calling canWin(5, memo):
  - memo[5] already has answer
  - Return memo[5] immediately (no recalculation!)

This is the OPTIMIZATION: cache hit = instant answer! ⚡

💡 Intuition - The Clever Conversion

PROBLEM IDENTIFIED in Brute Force:
  We keep recalculating divisorGame(3), divisorGame(2), etc.

SOLUTION:
  Cache (memoize) results the FIRST time we calculate them
  Next time we need same value → just look it up! 🎯

HOW TO IDENTIFY WHAT TO MEMOIZE:
  1. Look at function parameters → canWin(n, memo)
  2. Parameter 'n' changes with each recursive call
  3. For same 'n', result is always the same (deterministic game)
  4. So memoize using 'n' as the key! 🔑
  5. Key range: 1 to n

CONVERSION FROM BRUTE FORCE:
  1. Add a cache (array): memo[n]
     - memo[n] = true → player at position n wins
     - memo[n] = false → player at position n loses
  2. Use special value to mark "not calculated yet"
     - Can't use true/false (both valid answers)
     - Use Boolean[] (null = not calculated) ✨
  3. Before recursing, check cache
  4. Store result in cache before returning
  5. Same logic, just add caching!

🎯 Base Cases Transformation

BRUTE FORCE BASE CASES:
  if (n == 1) return false;  // Cannot move → lose

TOP-DOWN BASE CASES (SAME!):
  if (n == 1) return false;  // Cannot move → lose

Why same?
  - Base case defines the game-ending condition
  - "When n=1, current player cannot move and loses"
  - Memoization doesn't change the rules, only adds caching

ONLY ADDITIONS:
  1. Create memo array of Boolean[] (not boolean[])
     - Boolean can be null (not calculated)
     - boolean can only be true/false
  2. Initialize all to null
  3. Check cache before calculating
  4. Store result in cache before returning

IMPORTANT - Why Boolean[] not boolean[]:
  memo[i] states:
    - null: not calculated yet
    - true: player at position i wins
    - false: player at position i loses

  With boolean[], default is false
  Can't distinguish "not calculated" from "loses"! ⚠️

📝 Implementation

class Solution {
    public boolean divisorGame(int n) {
        // Create memoization cache
        // memo[i] = does player starting at position i win?
        // Use Boolean[] (not boolean[]) to distinguish null (not calculated)
        Boolean[] memo = new Boolean[n + 1];

        return canWin(n, memo);
    }

    private boolean canWin(int n, Boolean[] memo) {
        // Base case: n = 1, cannot make a move (SAME as brute force)
        if (n == 1) {
            return false;  // Current player loses
        }

        // ✨ NEW: Check if already calculated
        if (memo[n] != null) {
            return memo[n];  // Cache HIT! Return stored result
        }

        // Calculate (same game logic as brute force)
        // Try all possible moves
        for (int x = 1; x < n; x++) {
            // Check if x is a valid divisor
            if (n % x == 0) {
                // Make move: n becomes (n - x)
                // If opponent LOSES from (n - x), we WIN!
                if (!canWin(n - x, memo)) {
                    // ✨ NEW: Store in cache before returning
                    memo[n] = true;
                    return true;  // Found winning move!
                }
            }
        }

        // All moves lead to opponent winning
        // ✨ NEW: Store in cache before returning
        memo[n] = false;
        return false;  // We lose
    }
}

🔍 Detailed Dry Run: n = 5

Input: n = 5
Goal: Does Alice win?

Initial State:
memo = [null, null, null, null, null, null]  (size n+1 = 6)
        ↑     ↑     ↑     ↑     ↑     ↑
        0     1     2     3     4     5

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call: canWin(5, memo) - "Does player at position 5 win?"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Step 1: canWin(5, memo)
  n=5, not base case
  memo[5] = null → CACHE MISS
  Try all divisors of 5:
    - Divisors: 1, 5
    - Valid x (0 < x < 5): only x=1

  Try x=1:
    5 % 1 = 0 ✓ valid
    Check: !canWin(4, memo)
    Recurse → canWin(4, memo)

Step 2: canWin(4, memo) - "Does player at position 4 win?"
  n=4, not base case
  memo[4] = null → CACHE MISS
  Try all divisors of 4:
    - Divisors: 1, 2, 4
    - Valid x (0 < x < 4): x=1, x=2

  Try x=1:
    4 % 1 = 0 ✓ valid
    Check: !canWin(3, memo)
    Recurse → canWin(3, memo)

Step 3: canWin(3, memo) - "Does player at position 3 win?"
  n=3, not base case
  memo[3] = null → CACHE MISS
  Try all divisors of 3:
    - Divisors: 1, 3
    - Valid x (0 < x < 3): only x=1

  Try x=1:
    3 % 1 = 0 ✓ valid
    Check: !canWin(2, memo)
    Recurse → canWin(2, memo)

Step 4: canWin(2, memo) - "Does player at position 2 win?"
  n=2, not base case
  memo[2] = null → CACHE MISS
  Try all divisors of 2:
    - Divisors: 1, 2
    - Valid x (0 < x < 2): only x=1

  Try x=1:
    2 % 1 = 0 ✓ valid
    Check: !canWin(1, memo)
    Recurse → canWin(1, memo)

Step 5: canWin(1, memo) - "Does player at position 1 win?"
  n=1 → BASE CASE
  Return false (cannot move, lose)

  Back to Step 4

Step 6: Back at canWin(2, memo)
  Got canWin(1, memo) = false → "Opponent loses!"
  !false = true
  Found winning move! x=1 works
  Store: memo[2] = true ✓
  Return true

  memo = [null, null, true, null, null, null]
                      ↑
                   stored!

  Meaning: memo[2] = true means "Player at position 2 wins"

  Back to Step 3

Step 7: Back at canWin(3, memo)
  Got canWin(2, memo) = true → "Opponent wins!"
  !true = false
  x=1 doesn't work (opponent wins)
  No more valid x to try
  All moves failed
  Store: memo[3] = false ✓
  Return false

  memo = [null, null, true, false, null, null]
                            ↑
                         stored!

  Meaning: memo[3] = false means "Player at position 3 loses"

  Back to Step 2

Step 8: Back at canWin(4, memo)
  Got canWin(3, memo) = false → "Opponent loses!"
  !false = true
  Found winning move! x=1 works
  Store: memo[4] = true ✓
  Return true

  memo = [null, null, true, false, true, null]
                                   ↑
                                stored!

  Meaning: memo[4] = true means "Player at position 4 wins"

  Back to Step 1

Step 9: Back at canWin(5, memo)
  Got canWin(4, memo) = true → "Opponent wins!"
  !true = false
  x=1 doesn't work (opponent wins)
  No more valid x to try
  All moves failed
  Store: memo[5] = false ✓
  Return false

  Final memo = [null, null, true, false, true, false]
                                                 ↑
                                              stored!

  Meaning: memo[5] = false means "Player at position 5 loses"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: false (Alice LOSES) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Understanding memo values:
  memo[2] = true  → "Player at position 2 wins"
  memo[3] = false → "Player at position 3 loses"
  memo[4] = true  → "Player at position 4 wins"
  memo[5] = false → "Player at position 5 loses"

Pattern in memo:
  EVEN positions → true (win)
  ODD positions → false (lose)

Pattern discovered: EVEN wins, ODD loses! 🎯

📊 Complexity Analysis

Time Complexity: O(n²)

Each position 1 to n calculated EXACTLY ONCE: O(n)
For each position, try all divisors: O(n) in worst case
Total: O(n) × O(n) = O(n²)

Actually, trying divisors is faster:
  - Average number of divisors of n ≈ O(√n)
  - So realistic time ≈ O(n√n)

Still, upper bound is O(n²) ✓

Massive improvement from O(n!)! 🚀

Space Complexity: O(n)

Memoization array: O(n)
Recursion stack depth: O(n) worst case
Total: O(n) + O(n) = O(n)

---

🟢 Approach 3: Bottom-Up (Tabulation)

📐 Function Definition

DP Array Definition:

boolean[] dp = new boolean[n + 1];

What dp[i] represents:

Index i: - Position/state in the game - The number currently on the chalkboard - Example: i=4 means "board shows 4"

Value dp[i] (boolean): - dp[i] = true → Player whose turn it is at position i WINS - dp[i] = false → Player whose turn it is at position i LOSES - Example: dp[4] = true means "player at position 4 wins"

Purpose: - Store the answer for each position from 1 to n - Build solutions from smaller positions to larger ones - Bottom-up approach: start from base case, build to n

Key Understanding:

dp[3] = false means:
  "If it's my turn and the board shows 3, I will LOSE"

  Why?
    - Only valid move: choose x=1 → opponent gets 2
    - dp[2] = true → opponent wins
    - All my moves lead to opponent winning → I lose

dp[4] = true means:
  "If it's my turn and the board shows 4, I will WIN"

  Why?
    - Valid moves: x=1 or x=2
    - Choose x=1 → opponent gets 3
    - dp[3] = false → opponent loses
    - Found a move where opponent loses → I win!

Building dp table = answering "do I win?" for each position

💡 Intuition - The Clever Conversion from Top-Down

TOP-DOWN (Recursion + Memoization):
  Start from n → recurse down to smaller values → build back

  canWin(5, memo)
    ↓ needs
  canWin(4, memo)
    ↓ needs
  canWin(3, memo)
    ↓ needs
  canWin(2, memo)
    ↓ needs
  canWin(1, memo) = false (base case)

  Direction: TOP → DOWN to base, then back UP

BOTTOM-UP (Iteration + Tabulation):
  Start from base case → build up to n iteratively

  dp[1] = false (base case)
    ↓ build
  dp[2] = can I make move to reach dp[j] where dp[j]=false?
    ↓ build
  dp[3] = can I make move to reach dp[j] where dp[j]=false?
    ↓ build
  ...
    ↓ build
  dp[n]

  Direction: BOTTOM (base) → UP to n

KEY INSIGHT:
  For position i, check ALL valid moves:
    - For each divisor x of i (where 0 < x < i):
      - New position = i - x
      - If dp[i-x] = false (opponent loses) → dp[i] = true!

  If NO move makes opponent lose → dp[i] = false

🎯 Base Cases Transformation - VERY IMPORTANT! 🔑

TOP-DOWN BASE CASES (in recursion):
  if (n == 1) return false;  // Cannot move → lose

  This is a TERMINATION condition:
    "When we hit n=1 during recursion, return false immediately"

BOTTOM-UP BASE CASES (in DP table):
  dp[1] = false;  // Cannot move → lose

  This is an INITIALIZATION value:
    "Start with dp[1]=false, build from here"

KEY INSIGHT - THE CLEVER THINKING:
  1. In top-down: "What do I return when I can't recurse further?"
     → n=1 is the smallest case → return false

  2. In bottom-up: "What is the smallest subproblem I know?"
     → dp[1] is the smallest case → initialize to false

  3. The VALUE is the same (false), but the ROLE is different:
     - Top-down: BASE = where recursion STOPS
     - Bottom-up: BASE = where iteration STARTS

EXAMPLE:
  Top-down: if (n == 1) return false;
            ↓
  Bottom-up: dp[1] = false;

  Same value (false), different purpose! 🎯

HOW TO CONVERT:
  Step 1: Identify base case from top-down → dp[1] = false
  Step 2: Start iteration from i=2 (next position after base)
  Step 3: For each i, check all valid moves
  Step 4: If ANY move leads to dp[j]=false → dp[i]=true
  Step 5: Otherwise dp[i]=false

🔄 Recurrence Relation

Definition:
  dp[i] = does player starting at position i win?

For position i, try all valid moves:
  - For each x where (0 < x < i) AND (i % x == 0):
    - New position = i - x
    - If dp[i-x] = false → opponent loses → dp[i] = true!

If NO such move exists:
  dp[i] = false (all moves lead to opponent winning)

Formula:
  dp[i] = true  if EXISTS x: (0<x<i) AND (i%x==0) AND dp[i-x]=false
  dp[i] = false otherwise

Dependencies:
  dp[i] depends on dp[i-1], dp[i-2], ..., dp[1]
  (all smaller positions reachable in one move)

Must calculate in order: 1, 2, 3, ..., n
Can't skip ahead! Must build sequentially! 🎯

📝 Implementation

class Solution {
    public boolean divisorGame(int n) {
        // Create DP table
        // dp[i] = does player starting at position i win?
        boolean[] dp = new boolean[n + 1];

        // Initialize base case (VERY IMPORTANT!)
        // At position 1, cannot make a move → lose
        dp[1] = false;

        // Build up from base case to n
        // Start from 2 because we already know dp[1]
        for (int i = 2; i <= n; i++) {
            // Initially assume we lose
            dp[i] = false;

            // Try all possible moves
            for (int x = 1; x < i; x++) {
                // Check if x is a valid divisor
                if (i % x == 0) {
                    // Make move: i becomes (i - x)
                    // If opponent LOSES from (i - x), we WIN!
                    if (!dp[i - x]) {
                        dp[i] = true;  // Found winning move!
                        break;  // No need to check other moves
                    }
                }
            }
        }

        // Answer is at dp[n]
        return dp[n];
    }
}

🔍 Detailed Dry Run: n = 6

Input: n = 6
Goal: Does player starting at position 6 win?

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Create DP table:
dp = [false, false, false, false, false, false, false]
       ↑      ↑      ↑      ↑      ↑      ↑      ↑
       0      1      2      3      4      5      6

Initialize base case:
dp[1] = false (cannot move from position 1)

dp = [false, false, false, false, false, false, false]
              ↑
          base case ✓

Meaning: dp[1] = false → "Player at position 1 loses"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION - Building up to n
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Iteration 1: i = 2
━━━━━━━━━━━━━━━━
Question: "Does player at position 2 win?"

Position 2, try all divisors:
  Divisors of 2: 1, 2
  Valid x (0 < x < 2): only x=1

  Try x=1:
    2 % 1 = 0 ✓ valid
    New position: 2-1 = 1
    Check dp[1] = false ✓ "Opponent loses!"
    We win!

  dp[2] = true

dp = [false, false, true, false, false, false, false]
                    ↑
                 computed!

Meaning: dp[2] = true → "Player at position 2 wins"
  Strategy: Choose x=1 → opponent at position 1 → opponent loses


Iteration 2: i = 3
━━━━━━━━━━━━━━━━
Question: "Does player at position 3 win?"

Position 3, try all divisors:
  Divisors of 3: 1, 3
  Valid x (0 < x < 3): only x=1

  Try x=1:
    3 % 1 = 0 ✓ valid
    New position: 3-1 = 2
    Check dp[2] = true ✗ "Opponent wins!"
    Bad move!

  No winning move found
  dp[3] = false

dp = [false, false, true, false, false, false, false]
                          ↑
                       computed!

Meaning: dp[3] = false → "Player at position 3 loses"
  All moves lead to opponent winning


Iteration 3: i = 4
━━━━━━━━━━━━━━━━
Question: "Does player at position 4 win?"

Position 4, try all divisors:
  Divisors of 4: 1, 2, 4
  Valid x (0 < x < 4): x=1, x=2

  Try x=1:
    4 % 1 = 0 ✓ valid
    New position: 4-1 = 3
    Check dp[3] = false ✓ "Opponent loses!"
    We win!

  dp[4] = true (stop checking)

dp = [false, false, true, false, true, false, false]
                                ↑
                             computed!

Meaning: dp[4] = true → "Player at position 4 wins"
  Strategy: Choose x=1 → opponent at position 3 → opponent loses


Iteration 4: i = 5
━━━━━━━━━━━━━━━━
Question: "Does player at position 5 win?"

Position 5, try all divisors:
  Divisors of 5: 1, 5
  Valid x (0 < x < 5): only x=1

  Try x=1:
    5 % 1 = 0 ✓ valid
    New position: 5-1 = 4
    Check dp[4] = true ✗ "Opponent wins!"
    Bad move!

  No winning move found
  dp[5] = false

dp = [false, false, true, false, true, false, false]
                                       ↑
                                    computed!

Meaning: dp[5] = false → "Player at position 5 loses"
  All moves lead to opponent winning


Iteration 5: i = 6 (FINAL)
━━━━━━━━━━━━━━━━━━━━━━━━━
Question: "Does player at position 6 win?"

Position 6, try all divisors:
  Divisors of 6: 1, 2, 3, 6
  Valid x (0 < x < 6): x=1, x=2, x=3

  Try x=1:
    6 % 1 = 0 ✓ valid
    New position: 6-1 = 5
    Check dp[5] = false ✓ "Opponent loses!"
    We win!

  dp[6] = true (stop checking)

Final DP table:
dp = [false, false, true, false, true, false, true]
                                               ↑
                                           ANSWER!

Meaning: dp[6] = true → "Player at position 6 wins"
  Strategy: Choose x=1 → opponent at position 5 → opponent loses

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPLETE DP TABLE VISUALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Position:  0      1      2     3     4     5     6
         ┌─────┬──────┬─────┬─────┬─────┬─────┬─────┐
dp[]     │false│false │true │false│true │false│true │
         └─────┴──────┴─────┴─────┴─────┴─────┴─────┘
                 ↑      ↑     ↑     ↑     ↑     ↑
               base  WIN  LOSE WIN  LOSE  WIN

Understanding each value:
  dp[1] = false → "At position 1, player loses"
  dp[2] = true  → "At position 2, player wins"
  dp[3] = false → "At position 3, player loses"
  dp[4] = true  → "At position 4, player wins"
  dp[5] = false → "At position 5, player loses"
  dp[6] = true  → "At position 6, player wins"

Pattern Discovered:
  EVEN positions (2,4,6) → true (WIN)
  ODD positions (1,3,5) → false (LOSE)

PATTERN: EVEN positions WIN, ODD positions LOSE! 🎯

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: true (Alice starts at position 6 → Alice WINS) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

📊 State Transition Diagram

dp[i] depends on ALL smaller positions reachable in one move:

For position 6:
    dp[1]  dp[2]  dp[3]  dp[4]  dp[5]
     ↓      ↓      ↓      ↓      ↓
   (6-5) (6-4) (6-3) (6-2) (6-1)
     │      │      │      │      │
     └──────┴──────┴──────┴──────┘
                   ↓
                 dp[6]

Only divisors of 6 create valid edges:
  x=1: 6-1=5 → dp[5]=false ✓ (winning move!)
  x=2: 6-2=4 → dp[4]=true
  x=3: 6-3=3 → dp[3]=false ✓ (also winning!)

If ANY reachable position has dp[j]=false → dp[i]=true

Build sequentially from 1→n to ensure dependencies ready! 🎯

📊 Complexity Analysis

Time Complexity: O(n²)

Loop from 2 to n: O(n)
For each i, try divisors: O(n) worst case
Total: O(n) × O(n) = O(n²)

Actually faster in practice:
  Average divisors per number ≈ O(√n)
  Realistic: O(n√n)

Upper bound: O(n²) ✓

Space Complexity: O(n)

DP table of size (n+1): O(n)
No recursion stack: O(1)
Total: O(n)

---

🔵 Approach 4: Space-Optimized (Mathematical Pattern)

📐 Function Definition

Function Signature:

boolean divisorGame(int n)

What it represents:

Input Parameter n: - The initial number on the chalkboard - Starting position of the game - Example: n=100 means "game starts with 100 on board"

Return Value (boolean): - true = Alice (first player) WINS with optimal play - false = Alice (first player) LOSES with optimal play - Direct answer using mathematical pattern

Purpose: - Instantly determine winner using parity (even/odd) - No recursion, no DP table needed - O(1) solution based on mathematical proof

Key Understanding:

divisorGame(100) asks: "Does Alice win starting at 100?"

Pattern-based answer:
  100 is EVEN → return true

  Why?
    Mathematical proof shows:
      EVEN → first player wins
      ODD → first player loses

  No need to simulate the game!
  Just check: n % 2 == 0

This is the ULTIMATE optimization:
  From O(n²) DP to O(1) math! 🚀

💡 Intuition - Discovering the Pattern

From our DP table, we noticed:
  dp[1] = false (odd)
  dp[2] = true  (even)
  dp[3] = false (odd)
  dp[4] = true  (even)
  dp[5] = false (odd)
  dp[6] = true  (even)

PATTERN: n is EVEN → true, n is ODD → false

Can we prove this mathematically? 🤔

MATHEMATICAL PROOF:
━━━━━━━━━━━━━━━━━━
1. Base case: n=1 (odd) → false ✓

2. For EVEN n:
   - All divisors of even number include 1
   - Choose x=1 → new position = n-1 (odd)
   - Opponent at odd position loses
   - So even position wins! ✓

3. For ODD n:
   - All divisors of odd are also odd
   - Choose any odd x → new position = n-x (odd-odd = even)
   - Opponent at even position wins
   - So odd position loses! ✓

This proves: EVEN wins, ODD loses! 🎯

So we don't need DP at all - just check if n is even!

📝 Implementation

class Solution {
    public boolean divisorGame(int n) {
        // Mathematical solution: Alice wins if n is even
        return n % 2 == 0;
    }
}

🔍 Detailed Dry Run: n = 100

Input: n = 100

Question: "Does Alice win starting at position 100?"

Check: Is 100 even?
  100 % 2 = 0
  Yes, 100 is even!

Return: true

Result: Alice WINS! ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Why this works - Game simulation:
  n = 100 (EVEN, Alice's turn)

  Alice's strategy:
    - Always choose x=1 (always valid divisor)
    - 100 - 1 = 99 (ODD, Bob's turn)

  Bob at 99 (ODD):
    - Bob must choose odd divisor (1 is only option)
    - 99 - 1 = 98 (EVEN, Alice's turn)

  Alice at 98 (EVEN):
    - Choose x=1
    - 98 - 1 = 97 (ODD, Bob's turn)

  Pattern continues:
    100 → 99 → 98 → 97 → ... → 4 → 3 → 2 → 1

  Eventually:
    Alice at 2 (EVEN, Alice's turn)
    - Choose x=1
    - 2 - 1 = 1 (Bob's turn)

  Bob at 1 (ODD):
    - Cannot move (no valid x)
    - Bob LOSES!

  Alice WINS! ✓

Mathematical guarantee:
  EVEN → can always force opponent to ODD
  ODD → can only give opponent EVEN

  Alice starts with EVEN → she controls the game → she wins! 🎯

🎯 Why This Pattern Works - Mathematical Proof

THEOREM: Alice wins if and only if n is EVEN

PROOF BY INDUCTION:
━━━━━━━━━━━━━━━━━━

Base cases:
  n=1: odd → Alice loses (cannot move) ✓
  n=2: even → Alice wins (choose x=1, Bob at 1) ✓

Inductive step:
  Assume pattern holds for all k < n

  Case 1: n is EVEN
    - Divisors of EVEN include 1 (always)
    - Alice chooses x=1 → Bob at (n-1), which is ODD
    - By induction hypothesis, player at ODD loses
    - Bob loses → Alice WINS! ✓

  Case 2: n is ODD
    - All divisors of ODD are also ODD
    - Alice chooses any odd divisor x
    - New position = n-x = ODD-ODD = EVEN
    - By induction hypothesis, player at EVEN wins
    - All Alice's moves give Bob EVEN position
    - Bob wins from all moves → Alice LOSES! ✓

QED: EVEN wins, ODD loses! 🎯

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

WHY ODD - ODD = EVEN?
  Any odd number can be written as: 2k + 1 (for some integer k)

  n = 2a + 1 (n is odd)
  x = 2b + 1 (x is odd divisor)

  n - x = (2a + 1) - (2b + 1)
        = 2a - 2b
        = 2(a - b)
        = EVEN! ✓

This is why odd positions always lose:
  Can only move to even positions! 🎯

📊 Complexity Analysis

Time Complexity: O(1) ⭐

Single modulo operation
Constant time!

Improvement:
  O(n²) → O(1) 🚀🚀🚀
  MASSIVE speedup!

Space Complexity: O(1) ⭐

No array, no recursion
Just one boolean return
Constant space!

Improvement:
  O(n) → O(1) 🚀

---

🎯 Pattern Recognition - Game Theory DP

Core Pattern: Minimax Game Theory

Template for two-player game DP:

canWin(state) = true if EXISTS a move such that:
                  opponent LOSES from new state

canWin(state) = false if ALL moves lead to:
                  opponent WINS from new state

For Divisor Game:
  canWin(n) = true if EXISTS x: (0<x<n) AND (n%x==0) AND !canWin(n-x)
  canWin(n) = false otherwise

Similar Problems:
  - Nim Game: canWinNim(n) = (n % 4 != 0)
  - Stone Game: Optimal play with picking from ends
  - Predict the Winner: Two players picking from array

How to Identify Game Theory DP:

✅ Two players taking turns
✅ Both play optimally
✅ Win/lose based on game rules
✅ Current state determines future possibilities
✅ Recursive game tree structure

For Divisor Game:
  ✅ Alice and Bob alternate
  ✅ Both play optimally
  ✅ Cannot move → lose
  ✅ Position n determines valid moves
  ✅ Game tree from n → n-x → ...

Perfect for Game Theory DP! 🎯

BONUS: Sometimes has mathematical pattern!
  Look for even/odd, modulo, or number theory patterns

---

⚠️ Important Edge Cases to Test

1. Minimum Constraint: n = 1

Input: n = 1
Expected: false

Why important:
  - BASE CASE of the problem
  - Cannot make any move (no x where 0 < x < 1)
  - Tests base case handling

Function meaning:
  divisorGame(1) asks: "Does player at position 1 win?"
  Answer: false → "Player at position 1 loses"

Test all approaches:
  Brute Force: Base case returns false ✓
  Top-Down: memo[1] never set (base case) ✓
  Bottom-Up: dp[1] = false (initialization) ✓
  Pattern: 1 is ODD → false ✓

2. Minimum Winning Case: n = 2

Input: n = 2
Expected: true

Why important:
  - Smallest n where Alice wins
  - Only one valid move (x=1)
  - Tests simple winning scenario

Function meaning:
  divisorGame(2) asks: "Does player at position 2 win?"
  Answer: true → "Player at position 2 wins"

  Why?
    - Choose x=1 → opponent at position 1
    - divisorGame(1) = false → opponent loses
    - Found winning move → return true

Test all approaches:
  Brute Force: Finds x=1 leads to loss for opponent ✓
  Top-Down: memo[2] = true after calculation ✓
  Bottom-Up: dp[2] = true (dp[1]=false, found winning move) ✓
  Pattern: 2 is EVEN → true ✓

3. Small Odd Number: n = 3

Input: n = 3
Expected: false

Why important:
  - Smallest odd losing case
  - Tests odd number behavior
  - Validates pattern

Function meaning:
  divisorGame(3) asks: "Does player at position 3 win?"
  Answer: false → "Player at position 3 loses"

  Why?
    - Only valid move: x=1
    - Choose x=1 → opponent at position 2
    - divisorGame(2) = true → opponent wins
    - All moves lead to opponent winning → return false

Test all approaches:
  Brute Force: All moves (just x=1) lead to opponent win ✓
  Top-Down: memo[3] = false after checking all moves ✓
  Bottom-Up: dp[3] = false (dp[2]=true, no winning move) ✓
  Pattern: 3 is ODD → false ✓

4. Number with Multiple Divisors: n = 12

Input: n = 12
Expected: true

Why important:
  - Many divisors: 1, 2, 3, 4, 6
  - Tests optimal choice among multiple moves
  - Divisors include both even and odd

Function meaning:
  divisorGame(12) asks: "Does player at position 12 win?"
  Answer: true → "Player at position 12 wins"

  Why?
    Valid divisors: 1, 2, 3, 4, 6
    Possible new positions: 11, 10, 9, 8, 6

    Check each:
      x=1 → position 11 (odd) → divisorGame(11) = false ✓
      Found winning move!

Test all approaches:
  Brute Force: Tries all divisors, finds x=1 works ✓
  Top-Down: memo[12] = true (finds winning move) ✓
  Bottom-Up: dp[12] = true (11 is losing position) ✓
  Pattern: 12 is EVEN → true ✓

5. Prime Number: n = 7

Input: n = 7
Expected: false

Why important:
  - Prime has only one divisor: 1
  - Limited move options
  - Tests single-move scenarios

Function meaning:
  divisorGame(7) asks: "Does player at position 7 win?"
  Answer: false → "Player at position 7 loses"

  Why?
    - 7 is prime → only divisor is 1
    - Choose x=1 → opponent at position 6
    - divisorGame(6) = true → opponent wins
    - All moves (just one) lead to opponent winning → return false

Test all approaches:
  Brute Force: Only x=1 available, leads to opponent win ✓
  Top-Down: memo[7] = false (no winning move found) ✓
  Bottom-Up: dp[7] = false (dp[6]=true, no winning move) ✓
  Pattern: 7 is ODD → false ✓

6. Large Even Number: n = 1000

Input: n = 1000
Expected: true

Why important:
  - Maximum constraint boundary
  - Tests performance/correctness at scale
  - Large even number

Function meaning:
  divisorGame(1000) asks: "Does Alice win starting at 1000?"
  Answer: true → "Alice wins"

Test all approaches:
  Brute Force: O(1000!) - TOO SLOW ❌
  Top-Down: O(1000²) = 1,000,000 operations (acceptable) ✓
  Bottom-Up: O(1000²) = 1,000,000 operations (acceptable) ✓
  Pattern: 1000 is EVEN → O(1) instant! ✓✓✓

7. Large Odd Number: n = 999

Input: n = 999
Expected: false

Why important:
  - Near maximum constraint
  - Large odd number
  - Tests boundary behavior

Function meaning:
  divisorGame(999) asks: "Does Alice win starting at 999?"
  Answer: false → "Alice loses"

Test all approaches:
  Bottom-Up: Builds dp table to 999 ✓
  Pattern: 999 is ODD → false ✓

8. Power of 2: n = 16

Input: n = 16
Expected: true

Why important:
  - Special structure (2^4)
  - Divisors: 1, 2, 4, 8
  - Tests special number properties

Function meaning:
  divisorGame(16) asks: "Does player at position 16 win?"
  Answer: true → "Player wins"

  Many divisors, many winning paths:
    x=1 → 15 (odd, opponent loses) ✓
    x=2 → 14 (even, opponent wins)
    x=4 → 12 (even, opponent wins)
    x=8 → 8 (even, opponent wins)

  At least one winning move exists!

Test all approaches:
  All approaches work correctly ✓
  Pattern: 16 is EVEN → true ✓

9. Perfect Square: n = 9

Input: n = 9
Expected: false

Why important:
  - Perfect square (3²)
  - Divisors: 1, 3
  - Odd perfect square

Function meaning:
  divisorGame(9) asks: "Does player at position 9 win?"
  Answer: false → "Player loses"

  Divisors: 1, 3 (both odd)
  Possible positions: 8, 6 (both even)
  All moves lead to even positions (opponent wins)

Test all approaches:
  All approaches correctly identify no winning move ✓
  Pattern: 9 is ODD → false ✓

10. Consecutive Numbers: n = 4 and n = 5

Input: n = 4
Expected: true

Input: n = 5
Expected: false

Why important:
  - Tests alternating pattern
  - Consecutive even and odd
  - Validates even/odd rule

Function meaning:
  divisorGame(4) → true: "Player at 4 wins"
  divisorGame(5) → false: "Player at 5 loses"

  Shows the pattern flip between consecutive numbers

Test all approaches:
  Both values correctly computed by all approaches ✓
  Pattern: 4 EVEN → true, 5 ODD → false ✓

Summary - Edge Case Coverage

Category                  Test Cases       Pattern Result
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Minimum (n=1)             1                false (odd)
Small numbers             2,3,4,5          alternating
Multiple divisors         12               true (even)
Prime numbers             7                false (odd)
Large numbers             999, 1000        odd/even
Powers of 2               16               true (even)
Perfect squares           9                false (odd)
Boundary                  1, 1000          min/max

All cases validate: EVEN → true, ODD → false ✓

Function definition clarity:
  divisorGame(n) = "Does player at position n win?"
  Return: true/false based on optimal play

  Clear understanding prevents confusion! 🎯

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Two-player game. Players alternate choosing divisor x of n, then replacing n with n-x. Player who cannot move loses. Does Alice (first player) win?

Function Definition: - divisorGame(n) or canWin(n) = Does player at position n win with optimal play? - dp[i] = Does player at position i win with optimal play? - Return: true (wins) or false (loses)

Key Insight: This is a game theory DP problem. Player wins if they can make a move that puts opponent in losing position. Formula: canWin(n) = true if EXISTS x: (0<x<n) AND (n%x==0) AND !canWin(n-x)

PATTERN DISCOVERY: Alice wins if and only if n is EVEN! 🎯

Four Approaches: 1. Brute Force: Recursion trying all moves → O(n!) time ❌ 2. Top-Down: Add memoization → O(n²) time, O(n) space ✓ 3. Bottom-Up: Iterative DP table → O(n²) time, O(n) space ✓✓ 4. Mathematical: Check if even → O(1) time, O(1) space ⭐⭐⭐

⚡ Quick Implementation

public class Solution {
  public boolean divisorGame(int n) {
    // // Approach 1 - recursion
    // return recursive(n);

    // // Approach 2 - top down
    // Boolean[] memo = new Boolean[n + 1];
    // return topDown(n, memo);

    // Approach 3 - bottom up
    return bottomUp(n);

    // // Approach 4 - bottom up space optimized
    // return bottomUpSO(n);
  }

  private boolean bottomUpSO(int n) {
    return n % 2 == 0;
  }

  private boolean bottomUp(int n) {
    Boolean[] dp = new Boolean[n + 1];

    // base case
    dp[1] = false;

    for (int i = 2; i <= n; i++) {
      dp[i] = false;

      for (int x = 1; x < i; x++) {
        if (i % x == 0) {
          if (!dp[i - x]) {
            dp[i] = true;

            break;
          }
        }
      }
    }

    return dp[n];
  }

  private boolean topDown(int n, Boolean[] memo) {
    // same base case
    if (n == 1) {
      return false;
    }

    if (memo[n] != null) {
      return memo[n];
    }

    for (int x = 1; x < n; x++) {
      if (n % x == 0) {
        if (!topDown(n - x, memo)) {
          return memo[n] = true;
        }
      }
    }

    // Above never returned true, so return false
    return memo[n] = false;
  }

  private boolean recursive(int n) {
    // Think like alice started the game.
    // base case
    if (n == 1) {
      return false; // aiice loses when n = 1
    }

    // try all 0 < x < n
    for (int x = 1; x < n; x++) {
      if (n % x == 0) {
        // below f(n-x) is Bob turn
        // f(n) returns true if someone wins.
        // so if below function returns false Alice wins
        // if bob loses from any of moves, alice wins
        if (!recursive(n - x)) {
          return true;
        }
      }
    }

    // Above never returned true, so return false
    return false;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.divisorGame(2));
    System.out.println(s.divisorGame(3));
    System.out.println(s.divisorGame(4));
    System.out.println(s.divisorGame(5));
    System.out.println(s.divisorGame(6));
  }
}

🔑 Key Insights

Function Definitions Matter:

CLEAR: divisorGame(n) = "Does player at position n win?"
VAGUE: divisorGame(n) = "something about n"

dp[i] = "Does player at position i win?"
  true = wins
  false = loses

Without clear definition → confusion! ⚠️
With clear definition → easy to understand! ✓

Base Case:

dp[1] = false  (cannot make any move)

WHY?
  At position 1, need x where (0 < x < 1) AND (1 % x == 0)
  No such x exists!
  Cannot move → lose

  divisorGame(1) = false
  Meaning: "Player at position 1 loses"

Game Theory Recurrence:

dp[i] = true  if EXISTS valid move to losing position
dp[i] = false if ALL moves lead to winning positions

Valid move: (0 < x < i) AND (i % x == 0) AND dp[i-x] = false

WHY?
  "I win if I can make opponent lose"
  "I lose if opponent wins no matter what I do"
  Classic minimax pattern! 🎯

Mathematical Pattern:

EVEN → true (Alice wins)
ODD → false (Alice loses)

WHY?
  EVEN: Can choose x=1 → opponent gets ODD → opponent loses
  ODD: All divisors are ODD → opponent gets EVEN → opponent wins

Proven by mathematical induction! ✓

Memoization Note:

Use Boolean[] not boolean[]

WHY?
  Boolean can be null → "not calculated"
  boolean defaults to false → can't distinguish!

memo[i] states:
  - null: not yet calculated
  - true: position i wins
  - false: position i loses

🎪 Memory Aid

"Even is heaven, odd is not!"
"Player at position asks: do I win?"
"dp[i] means: position i wins or loses!"
"Math beats DP - check parity!" ✨

⚠️ Common Mistakes

• ❌ Confusing what dp[i] represents (position vs player)
• ❌ Using boolean[] instead of Boolean[] in memoization
• ❌ Including n itself as valid divisor (must be x < n)
• ❌ Thinking DP is required (pattern solution is O(1)!)
• ❌ Not understanding function return value meaning

✅ Interview Talking Points

"This is a game theory problem with optimal play.

Function Definition:
  divisorGame(n) = Does the player at position n win?
  dp[i] = Does the player at position i win?
  Clear definition prevents confusion!

DP Approach:
  1. Base case: dp[1] = false (cannot move, loses)
  2. Recurrence: dp[i] = true if any move leads to dp[j]=false
  3. Try all divisors x of i, check dp[i-x]
  4. Build from 1 to n

Pattern Discovery:
  After solving with DP, notice: EVEN wins, ODD loses

Mathematical Proof:
  - EVEN: choose x=1 → opponent gets ODD → wins
  - ODD: all divisors odd → opponent gets EVEN → loses

Optimal Solution:
  return n % 2 == 0;  // O(1) time and space!

Why DP still useful:
  - Systematic approach to discover pattern
  - Clear function definitions aid understanding
  - Works for variations without closed formula

Complexity: DP is O(n²) time, O(n) space
            Pattern is O(1) time, O(1) space ⭐"

---

🎉 Congratulations!

You've mastered Divisor Game with crystal-clear function definitions!

What You Learned:

✅ Function Definition Clarity - Knowing what parameters and returns mean
✅ Game Theory DP - Win if opponent loses, lose if opponent wins
✅ Minimax Pattern - Optimal play for both players
✅ Boolean Memoization - Using Boolean[] for null state
✅ Pattern Discovery - Even/odd mathematical insight
✅ Proof by Induction - Mathematical correctness guarantee
✅ O(1) Optimization - From O(n²) to constant time!

The Power of Clear Definitions:

WITHOUT clear function definition:
  "What does divisorGame(5) return?" 🤔
  "Does it mean Alice wins or current player wins?" 🤔
  "What about dp[i]? What does it represent?" 🤔

WITH clear function definition:
  divisorGame(5) = "Does player at position 5 win?"
  Return: false (player at 5 loses)
  dp[i] = "Does player at position i win?"

  Crystal clear! No ambiguity! ✓🎯

Pattern Evolution:

Problem 205: Counting (Fibonacci)
  ways(n) = ways(n-1) + ways(n-2)
  Definition: "Number of ways to reach step n"

Problem 206: Optimization (Min cost)
  dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
  Definition: "Minimum cost to reach step i"

Problem 207: Game Theory (Minimax)
  dp[i] = true if EXISTS move to dp[j]=false
  Definition: "Does player at position i win?"

Clear definitions for ALL! 💪

You've now mastered function definitions in DP! This clarity will help in ALL future problems! 🚀✨