The original problem

1025. Divisor Game

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

1025. Divisor game

Alice and Bob take turns playing a game, with Alice taking the lead.

At the beginning, there is a number on the board n. During a player’s turn, that player does the following:

  • Select any integer x such that 0 < x < N and N % x == 0
  • Replace the number N on the blackboard with N minus x

Finally, if the player has no choice, then the game fails.

Return True if and only if Alice wins the match, assuming both players are at their best

Example 1:

Input: 2 Output: true Description: Bob cannot operate when Alice selects 1. Example 2:

Input: 3 Output: false Description: Alice selects 1, Bob also selects 1, and Alice cannot operate.

Tip:

1 <= N <= 1000

  • This is under dynamic programming in LeetCode

Analysis of the question

Combined with the official classification of LeetCode, we can guess that the solution idea of this problem is more inclined to the idea of dynamic programming, which is the core of dynamic programming, and the results are interdependent. At least one idea is dynamic programming direction (if you know the Solution of Fibonacci numbers, it is easy to associate the specific idea of dynamic programming in this problem. For those of you who don’t understand Fibonacci numbers, please follow my leetCode post on Question 509.) . Or another way to think about it, if you plug in the numbers, it’s not hard to find a conclusion, that even numbers are bound to win, odd numbers are bound to lose. Let’s think about how to prove this.

Method 1: dynamic programming

Ideas:

When N is 1:

No number x can be put in, enter

When N is 2:

X equals 1 wins.

When N is 3:

If x is 1, the new N of the opponent’s turn is 2. According to the above derivation, if N is 2, the opponent wins and he loses, continue to try to change X

If x is 2, it’s not divisible

When N is 4:

If x is 1, the opponent’s new turn N is 3. According to the above derivation, when N is 3, the opponent loses and he wins, and there is no need to continue trying to change x.

Pseudo code:

Boolean array (N+1); Boolean array (N+1); Boolean array (N+1); The second loop runs from 1 to the current outer loop array x (excluding x), from small to large; If i.n % x ==0 is divisible, the opponent will be judged to win[n-x] in the next round. If the opponent loses, it will naturally win in the current round. The result will be stored in the array win[n] II. Otherwise, I continues to be tried after x increases; 3. At the end of traversal, the winning and losing results from 2 to N are kept in the array, and return win[N];Copy the code
  • Note: The submitted results of dynamic planning are correct on the whole, but it is not efficient in terms of time and space complexity due to the large number of cycles. The actual project needs to select the algorithm according to the specific scene

Dynamic planning implementation code:


	public boolean divisorGame(int N) {
		boolean[] win = new boolean[N + 1];
		for (int n = 2; n <= N; ++n) {
			for (int x = 1; x < n; x++) {
				if (n % x == 0) {
					if(! win[n - x]) { win[n] =true;
						break; }}}}return win[N];
	}

Copy the code

Method two: prove according to odd-even law

Ideas:

When N is 1, win

When N is 2, win

If N is 3, it loses

When N is 4: win

.

It is found that if N is odd, win and N is even, lose, then it is transformed into mathematical problem proof.

Proof:

1. If N is odd, 1.N is prime, then x must be only 1. 2.N is not prime, if x exists, then x must be odd, and N becomes n-x, which is an even number with a smaller number; Conclusion: When N is odd, opponent turns must be even and N decreases. 2. If N is even, we win: 1. If x is equal to 1, N becomes n-1, which is an odd number with smaller numbers; 2. The N of the opponent's turn must be an odd number, so we can know that our N must be a reduced even number after the operation, and we keep x=1; 3. In the final round, opponent N decreases to 1, opponent loses and we win; Conclusion: we win when N is even. 2. If N is odd, we lose: 1. If N is prime, then x must be only 1, and the opponent turns into an even number. 2. If N is not prime and x exists, then x must be odd, and the opponent turns N into n-x, which is an even number with smaller numbers. According to one, the opponent sets x=1 and the opponent wins, and we lose. Conclusion: when N is odd, we lose.Copy the code

Implementation code:

	public boolean divisorGame(int N) {
		return (N & 1) == 0;
	}
	
Copy the code

eggs

When you look closely at the implementation of the second method, instead of using N % 2 == 0 to determine parity, you use (N & 1) == 0 to determine parity, which is the Easter egg in this article. A journey of a thousand miles begins with a single step