leetcode-cn Daily Challenge on July 24th, 2020.
Difficulty : Easy
Related Topics : Math、Dynamic Programming
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
with0 < x < N
andN % x == 0
.- Replacing the number
N
on the chalkboard withN - 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.
Input: 2 Output: true Explanation: Alice chooses 1, and Bob has no more moves.
Input: 3 Output: false Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
1 <= N <= 1000
- mine
- Java
Runtime: 0 ms, faster than 100.00%, Memory Usage: 35.9 MB, less than 84.88% of Java online submissions
// O(1)time // O(1)space //if you want to win, you will make the last you face is 2. // when N is odd, whatever your choose, N will be even. // if N is even, you just make N change to odd. so your next N is also even. // final you will got 2, and you choose 1, and you win. public boolean divisorGame(int N) { return N % 2 == 0; }
- Java