# Divisor Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/divisor-game)
Canonical: https://scaleengineer.com/dsa/problems/divisor-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Companies:** [Visa](https://scaleengineer.com/companies/visa)
---
## Problem
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, and Bob has no more moves.

**Example 2:**

**Input:** n = 3
**Output:** false
**Explanation:** Alice chooses 1, Bob chooses 1, and Alice has no more moves.

**Constraints:**

* `1 <= n <= 1000`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the game. We determine the winner for each number `i` from 1 up to `n`. A player wins from a state `i` if they can make a move to a state `j` from which the other player is guaranteed to lose.
**Time:** O(n^2). The outer loop runs `n` times, and the inner loop runs up to `n` times for each `i`. This gives a quadratic time complexity. · **Space:** O(n) to store the results for `n` subproblems in the DP array.
**Pros:** It's a general and intuitive approach for solving impartial games.; Guaranteed to find the optimal solution.
**Cons:** Not the most efficient solution for this specific problem.; The `O(n^2)` time complexity might be too slow for larger `n`, but it's acceptable for `n <= 1000`.
### Explanation
We can solve this game theory problem using a bottom-up dynamic programming approach. The state of the game is defined by the current number `n` on the chalkboard.

Let `dp[i]` be a boolean value indicating if the current player can win starting with the number `i`.
*   `dp[i] = true` means the current player can win.
*   `dp[i] = false` means the current player will lose if the opponent plays optimally.

The goal is to compute `dp[n]`.

*   **Base Case:** For `n = 1`, there are no valid moves (`0 < x < 1` is impossible). So, the player whose turn it is loses. `dp[1] = false`.

*   **Transitions:** For any number `i > 1`, the current player wins if they can make a move to a number `i - x` (where `x` is a proper divisor of `i`) from which the other player loses. In other words, `dp[i]` is `true` if there exists a divisor `x` of `i` such that `dp[i - x]` is `false`.

We can build up the `dp` table from `i = 2` to `n`.

```java
class Solution {
    public boolean divisorGame(int n) {
        boolean[] dp = new boolean[n + 1];
        // In Java, boolean arrays are initialized to false.
        // So dp[1] is already false.
        
        for (int i = 2; i <= n; i++) {
            for (int x = 1; x < i; x++) {
                if (i % x == 0) {
                    // Check if moving to i-x is a winning move.
                    // A move is winning if the opponent is left in a losing state.
                    // A losing state for the opponent is one where dp[state] is false.
                    if (!dp[i - x]) {
                        dp[i] = true;
                        break; // Found a winning move, no need to check further for this i.
                    }
                }
            }
        }
        return dp[n];
    }
}
```
### Algorithm
*   Create a boolean DP array `dp` of size `n + 1`, initialized to `false`.
*   Loop `i` from 2 to `n`.
*   Inside this loop, loop `x` from 1 to `i-1`.
*   If `i` is divisible by `x`, check the value of `dp[i - x]`.
*   If `dp[i - x]` is `false`, it means we found a move to a losing position for the opponent. Set `dp[i] = true` and break the inner loop.
*   After the loops complete, return `dp[n]`.

## Mathematical Approach
A closer look at the game's rules and states reveals a simple pattern. The winner can be determined just by the parity of the initial number `n`. This approach leverages this mathematical insight for a highly efficient solution.
**Time:** O(1). The solution involves a single modulo operation, which is a constant time operation. · **Space:** O(1). No extra space is required.
**Pros:** Extremely efficient in both time and space.; Very simple to implement.
**Cons:** Relies on a mathematical insight that might not be immediately obvious.; It's less of a general algorithmic approach and more of a problem-specific trick.
### Explanation
By analyzing the game, we can deduce a simple mathematical rule that determines the winner.

Let's prove by induction that the first player (Alice) wins if `n` is even and loses if `n` is odd.

*   **Base Cases:**
    *   `n = 1`: `n` is odd. Alice has no moves and loses. The rule holds.
    *   `n = 2`: `n` is even. Alice chooses `x=1`, `n` becomes `1`. Bob receives `1` and loses. Alice wins. The rule holds.

*   **Inductive Hypothesis:** Assume for all integers `k < n`, the current player wins if `k` is even and loses if `k` is odd.

*   **Inductive Step:**
    *   **Case 1: `n` is odd.**
        Alice must choose a divisor `x` of `n`. Since `n` is odd, all of its divisors `x` must also be odd. The new number becomes `n - x`. The difference between two odd numbers (`n` and `x`) is always an even number. So, Alice must pass an even number to Bob. By the inductive hypothesis, Bob receives an even number and wins. Since every move Alice makes leads to a winning position for Bob, Alice will lose if `n` is odd.
    *   **Case 2: `n` is even.**
        Alice can simply choose `x = 1` (which is always a divisor for `n > 1`). The new number becomes `n - 1`. Since `n` is even, `n - 1` is odd. Alice can pass an odd number to Bob. By the inductive hypothesis, Bob receives an odd number and loses. Since Alice can make a move that forces Bob into a losing position, Alice will win if `n` is even.

Thus, the proof is complete. Alice wins if and only if `n` is even.

```java
class Solution {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}
```
### Algorithm
*   Check if the input number `n` is even.
*   If `n` is even, return `true`.
*   If `n` is odd, return `false`.
*   This can be implemented with a single expression: `n % 2 == 0`.

# Solutions
### Java

```java
class Solution {
public
  boolean divisorGame(int n) { return n % 2 == 0; }
}

```

### JavaScript

```javascript
var divisorGame = function ( n ) { return n % 2 === 0 ; };
```

### CPP

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

```

### Python

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

```