1025. Divisor Game (C++)

Comments

Problem Setting

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.

image

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 from Ho Ngan Hang

In [1]:
#include <iostream>
using namespace std;

class Solution {
public:
    bool divisorGame(int N) {
        vector<bool> v(N + 1);
        for (int i = 0; i < N; i++) {
            if (!v[i]) {
                for (int j = 1; i + j <= N && j < i + j; j++)
                    if ((i + j) % j == 0)
                        v[i + j] = 1;
            }
        }
        return v[N];
    }
};
In [2]:
Solution S;
// Example 1
S.divisorGame(2)
Out[2]:
true
In [3]:
// Example 2
S.divisorGame(3)
Out[3]:
false

Step-by-step understanding 

// Step. 1 
// - Define the function with input integer N
// - this returns N's element 
bool divisorGame(int N) {
// ...
}
return v[N];    

// Step. 2
// initialize boolean array of N + 1 
vector<bool> v(N + 1);

// Step. 3
// - for loop for `i` from 0 to N-1
for (int i = 0; i < N; i++) {
...
}

// Step. 4
// - if i's element is not null, which means it is not calclated be fore
if (!v[i]) {
}

// Step. 5
// - another for loop for `j` from 1 to i+j
    for (int j = 1; i + j <= N && j < i + j; j++)

// Step. 6
// if i + j can be divided by j i.e., j is divisor for i + j 
        if ((i + j) % j == 0)

// Step. 7
// Insert 1 at i+j's element in v
            v[i + j] = 1;

Comments

Comments powered by Disqus