Divisor Game
Real-world version: Who Wins the Shrinking CounterThe statement here is our own: the same inputs, outputs and technique.
A counter starts at n. Two players take turns and the first player goes first.
On a turn a player picks a whole number below the counter and above nothing that divides the counter evenly, then lowers the counter by that amount. A player with no legal pick loses.
Both play as well as they can. Return whether the first player wins.
Examples
Example 1
- Input
- n = 6
- Output
- true
Six is even, so the first player lowers it by one and hands over five. Five is odd, so whatever the other player picks leaves an even counter, and the first player keeps handing odd counters back until the other player faces a counter of one.
Example 2
- Input
- n = 1
- Output
- false
There is no legal pick at all, since a pick has to sit below the counter and above nothing, so the first player loses at once.
Example 3
- Input
- n = 999
- Output
- false
An odd counter has only odd divisors, so the first player must hand over an even counter and the other player takes the winning side.
Constraints
- 1 <= n <= 1000
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def divisor_game(n: int) -> bool:public boolean divisorGame(int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's