# LeetCode 1025: Divisor Game

## Problem Restatement

Alice and Bob play a game.

They start with the number `n`.

On each turn, the current player chooses a number `x` such that:

```python
0 < x < n
n % x == 0
```

Then `n` is replaced by `n - x`.

The player who cannot make a move loses.

Alice always goes first. Both players play optimally.

Return `true` if Alice wins, `false` if Bob wins.

The official constraints state that `1 <= n <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | `true` if Alice wins |
| Rule | Choose divisor `x` of current `n`, replace `n` with `n - x` |
| Lose | Cannot make a move |

Function shape:

```python
def divisorGame(n: int) -> bool:
    ...
```

## Examples

Example 1:

```python
n = 2
```

Alice picks `x = 1` (only valid choice). `n` becomes `1`. Bob has no valid move (no `x` with `0 < x < 1`). Alice wins.

Answer:

```python
True
```

Example 2:

```python
n = 3
```

Alice must pick `x = 1`. `n` becomes `2`. Bob picks `x = 1`. `n` becomes `1`. Alice has no valid move. Bob wins.

Answer:

```python
False
```

## Key Insight

Alice wins if and only if `n` is even.

**Proof by induction:**

Base cases:
- `n = 1`: No valid move for Alice. Alice loses. (Odd → lose.)
- `n = 2`: Alice picks `x = 1`, `n` becomes `1`. Bob loses. (Even → win.)

Inductive step:
- If `n` is odd: any divisor `x` of an odd number is odd (odd numbers have only odd divisors). So `n - x` is even. Bob receives an even number and wins by induction. Alice loses.
- If `n` is even: Alice picks `x = 1`. `n - 1` is odd. Bob receives an odd number and loses by induction. Alice wins.

## Algorithm

```python
return n % 2 == 0
```

## Correctness

See the proof above.

For even `n`:
- Alice plays `x = 1`, leaving `n - 1` (odd) for Bob.
- Bob, receiving an odd number, will eventually lose.

For odd `n`:
- Any divisor of an odd number is odd.
- `n - x` is always even (odd minus odd).
- Bob always receives an even number and wins.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | Single check |
| Space | `O(1)` | No storage |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0
```

## Code Explanation

The entire logic is a single parity check:

```python
return n % 2 == 0
```

Even `n` is a winning position for Alice. Odd `n` is a losing position.

## Alternative: Dynamic Programming

We can also verify this with DP for small `n`:

```python
class Solution:
    def divisorGame(self, n: int) -> bool:
        dp = [False] * (n + 1)
        for i in range(2, n + 1):
            for x in range(1, i):
                if i % x == 0 and not dp[i - x]:
                    dp[i] = True
                    break
        return dp[n]
```

This confirms the pattern: `dp[i]` is `True` for all even `i`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.divisorGame(2) == True
    assert s.divisorGame(3) == False
    assert s.divisorGame(1) == False
    assert s.divisorGame(4) == True
    assert s.divisorGame(100) == True
    assert s.divisorGame(999) == False

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `2` | `True` | Even, Alice wins |
| `3` | `False` | Odd, Bob wins |
| `1` | `False` | No valid move for Alice |
| `4` | `True` | Even, Alice wins |
| `100` | `True` | Even |
| `999` | `False` | Odd |