879. Divisor Duel
A chalkboard shows the positive integer n. Two students alternate turns, the first student starting. On a turn the current student must pick an integer x with 0 < x < n such that n % x == 0, then erase n and write n - x instead. A student who cannot make a legal choice (this happens when the board shows 1) loses.
Both students play optimally. Return true if the first student wins, false otherwise.
Hint for the intended solution: a simple dynamic program over all values up to n is too slow for the largest inputs; find the pattern.
Example 1
- Input:
- n = 6
- Output:
- true
- Explanation:
6 is even: subtracting 1 leaves 5, and from any odd number every move leaves an even number again, so the first player keeps handing back odd numbers until the rival is stuck at 1.
Example 2
- Input:
- n = 9
- Output:
- false
- Explanation:
9 is odd, so every move subtracts an odd divisor and hands the rival an even number; the first player eventually gets stuck at 1 and loses.
Constraints
- 1 ≤ n ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(1)
- Space
- O(1)