LeetCode 1025. Divisor Game (Eas

Description
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: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:
Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

1 <= N <= 1000

Solution 1 - Mathematical Induction (credit to Junaid Mansuri):

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

Explanation:
The proof of why this works can be done formally using Mathematical Induction, specifically using Strong Mathematical Induction. However an informal proof will also suffice. Note that it is not enough to show that a player who starts on even always wins. One must also show that a player that starts on odd always loses. Otherwise there are more possible ways to guarantee winning aside from starting on even.

Given: The Divisor Game as outlined in the problem

Prove: Alice will win if and only if N % 2 == 0

Part 1) If Alice starts with an even number she will always win.

If Alice has an even number, she can always subtract 1, giving Bob an odd number. Odd numbers are not divisible by 2. They are only divisible by odd numbers. Hence Bob must subtract an odd number. Since odd minus odd is even, Bob will always return an even number to Alice. Alice will thus get a smaller even number after each round of play and Bob will get a smaller odd number after each round of play. Eventually Bob will have to play the number 1 and will lose the game since he will have no options.

Part 2) If Alice starts with an odd number she will always lose.

If Alice has an odd number, she has no choice but to subtract an odd number as odd numbers have no even divisors. Thus Bob will get an even number. Now using the argument from Part 1 above, Bob can take this even number and keep giving an odd number back to Alice by subtracting 1. Thus Bob will always get to play even and Alice will always be stuck with an odd number smaller than her previous odd number after each round. Eventually Alice will have to play the number 1 and will lose the game since she will have no options.

Thus, assuming both players play optimally, Alice will win the game if and only if she starts on an even number (i.e. N % 2 == 0).

Solution 2 - Dynamic Programming(credit to dj_khaled
))

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

Explanation (Credit to Jaspal1303)

dp is the array that is storing the memoized solution for Dynamic Programming. This is a bottom up DP meaning we will use the results for smaller sub-problems to find the result for N. dp[i]=True if the player starting with number i wins, else False

1. Initialize solution as false till (N+1). N+1 because index 0 is ignored.
2. Outer Loop (index i) from 1 to N (inclusive) and fill up the table till n. At the end, we will return dp[n] as answer
3. Inner loop (index j) finds the divisor for index i. We only need to find divisor up to i//2 because a number j greater than i//2 can't give i%j==0
4. Once we find an index j that divides i, we got a j that Alice can pick but is that optimal? It is optimal if i-j is not losing for Alice, meaning when Bob gets i-j dp[i-j] must be False. When both these conditions are met we set dp[i]=True.
5. We break the loop because we only need to find one such j that can make Alice win the game.