1030EasyMathDynamic ProgrammingBrainteaserGame TheoryImpartial Game

Who Wins the Shrinking Counter

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def divisor_game(n: int) -> bool:

Java

public boolean divisorGame(int n)

The intended approach

Time O(1).Space O(1).

Settle the counters from the bottom up. A counter of one offers no legal pick, so whoever faces it loses. For any larger counter, the player to move wins exactly when some legal pick hands the other player a losing counter. Filling that in upward shows the pattern outright: the player to move wins precisely when the counter is even. An even counter always allows a pick of one, which hands over an odd counter. An odd counter has only odd divisors, so lowering it by any of them leaves an even counter behind, which the other player then wins from. The two cases feed each other all the way up, so the whole thing collapses to the counter's evenness. That leaves one comparison, and the table is only needed to see why.

Pythonentry point: divisor_game

def divisor_game(n):
    return n % 2 == 0

The obvious version

Build the table the pattern came from. Work up from a counter of two, and for each one try every divisor below it, marking the counter a win when some pick leaves the other player a counter already marked a loss. Costs the counter squared rather than a single comparison.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_divisor_game(n):
    wins = [False] * (n + 1)
    for value in range(2, n + 1):
        got = False
        for x in range(1, value):
            if value % x == 0 and not wins[value - x]:
                got = True
                break
        wins[value] = got
    return wins[n]

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in