It is Thursday and the workweek is almost done. Continue to walk with my wife every morning unless it is raining. Today it was 75F and 75% relative humidity. The conditions were not the best, but we completed our walk. On my way back I watered the plants. It takes me less than 5 minutes.
The lawns in the neighborhood have patches of dried grass. Most lawns have sprinklers but between the heat and the lack of rain, I would venture to say that about 15% of the grass in most (never say all) laws is yellowish indicating it is very dry.
The saga with the presidential elections in Peru continues. Contrary to what the news from American sources (i.e., Reuters, The Guardian, and The New York Times) state, there has been massive fraud and it seems that the communist candidate will win using fraud. Have we seen this before?
Earlier today I gave a try to the LeetCode 1025 Divisor Game problem. It is ranked easy.
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: o Choosing any x with 0 < x < n and n % x == 0. o 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. Hint: If the current number is even, we can always subtract a 1 to make it odd. If the current number is odd, we must subtract an odd number to make it even.
Both players use the same approach.
The number n is swapped with n – x on each play. The value for x must meet two constraints. Note that a different way of looking at n % x == 0 is to state that x is a factor of n. For example, if n = 100 then x could be 1, 2, 4, 5, 25, and 50.
public boolean divisorGame(int n) {
}
I will solve the problem using the Java programming language and the VSCode IDE on a Windows computer. Your choice of computer platform and IDE should not affect the Java code.
I will solve the problem on my computer instead of using the IDE provided by LeetCode. That said; we will need to develop a test scaffold to collect the input value of `n`, make the call to the function of interest, and display the result.
2 <<< memo: [-1, 0, -1] main <<< n: 2 divisorGame: Alice main <<< execution time: 1 ms main <<< n: 2 divisorGame1: Alice main <<< execution time: 0 ms Explanation: Alice chooses 1, and Bob has no more moves. 3 <<< memo: [-1, 0, 1, -1] main <<< n: 3 divisorGame: Bob main <<< execution time: 1 ms main <<< n: 3 divisorGame1: Bob main <<< execution time: 0 ms Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves. 11 <<< memo: [-1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, -1] main <<< n: 11 divisorGame: Bob main <<< execution time: 1 ms main <<< n: 11 divisorGame1: Bob main <<< execution time: 0 ms 1000 <<< memo: [-1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, -1] main <<< n: 1000 divisorGame: Alice main <<< execution time: 10 ms main <<< n: 1000 divisorGame1: Alice main <<< execution time: 1 ms
The input line contains the value for `n`. It seems that at some point we use memoization in our dynamic problem.
It seems that we have two implementations for the solution. Both seem to return the same result. The execution time of the first implementation seems to be slower than the second.
Please note that displaying the values of the memo are not part of the solution. That said; it will help us generate a second approach without using tabulation.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
long start = 0;
long end = 0;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read n ****
int n = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// **** check if n is out of range ****
if (n < 1 || n > 1000) {
System.out.println("main <<< unexpected n: " + n);
System.exit(-1);
}
// **** play game and display winner ****
start = System.currentTimeMillis();
System.out.println("main <<< n: " + n + " divisorGame: " + (divisorGame(n) ? "Alice" : "Bob"));
end = System.currentTimeMillis();
System.out.println("main <<< execution time: " + (end - start) + " ms");
// **** play game and display winner ****
start = System.currentTimeMillis();
System.out.println("main <<< n: " + n + " divisorGame1: " + (divisorGame1(n) ? "Alice" : "Bob"));
end = System.currentTimeMillis();
System.out.println("main <<< execution time: " + (end - start) + " ms");
}
The test code is quite simple. We read the input line, assign the value to `n` and call the two implementations of the function of interest. For each we display the result and the time it took to execute.
/**
* 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:
*
* o Choosing any x with 0 < x < n and n % x == 0.
* o 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.
*
* Runtime: 6 ms, faster than 8.35% of Java online submissions.
* Memory Usage: 35.6 MB, less than 66.11% of Java online submissions.
*/
static boolean divisorGame(int n) {
// **** initialization ****
int memo[] = new int[n + 1];
Arrays.fill(memo, -1);
// **** make recursive call ****
boolean ans = divisorGameHelper(n, memo) == 1 ? true : false;
// ???? ????
System.out.println("<<< memo: " + Arrays.toString(memo));
// **** return answer ****
return ans;
}
This is the entry point for the recursive method. On my first pass I did not have the memo array used for memoization. Memoization was added in order to speed up the operation of the recursive call.
/**
* Recursive call.
* Time: O(2^n) without memoization
*
* Using memoization.
* Time:
*/
static private int divisorGameHelper(int n, int[] memo) {
// **** player cannot make a move (base condition) ****
if (n <= 1) return 0;
// **** check memo (if needed) ****
if (memo[n] != -1) return memo[n];
// **** try all factors ****
for (int x = 1; x <= (n / 2); x++) {
// **** check if x is a factor of n ****
if (n % x == 0) {
// **** recursive call (update memo) ****
memo[n - 1] = divisorGameHelper(n - 1, memo);
// **** check if next player cannot make a move ****
if (memo[n - 1] == 0)
return 1; // game won
}
}
// **** game lost *****
return 0;
}
The recursive call starts with a base case. The base case was generated based on the requirements.
We check the memo array and if the value is found; then we can return it. Note that if you comment out this line you will experience the actual speed of this function. Give it a try and you will enable this line. It is quite slow. Check the comments section of the function.
We enter a loop in which we test all values of `x`. For each value we only take the ones that are factors of n.
For each factor we make a recursive call simulating the next move in the game.
We then save the result in the memo array. If the next call fails; then the game was won by Alice; otherwise the game continues.
If we end the loop then we indicate that Alice lost the game because there were no valid moves available.
/**
* 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:
*
* o Choosing any x with 0 < x < n and n % x == 0.
* o 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.
*
* Time: O(n) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 35.6 MB, less than 77.92% of Java online submissions.
*/
static boolean divisorGame1(int n) {
return (n % 2 == 0);
}
By looking at the contents of the `memo` one can figure out that Alice always wins when `n` is even and Bob when `n` is odd. I was going to implement a function using tabulation but given the code that was accepted by LeetCode; I decided to skip it. If you implement such version of the function in questions, please leave me a copy and I will update this post.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John