0688EasyMathBrainteaserMinimaxGame TheoryNim GameImpartial Game

Taking the Last Tile

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 single stack holds count tiles. You and one opponent take turns, and you take the first turn. On a turn the player whose turn it is removes 1, 2 or 3 tiles from the stack; a player may never pass and may never remove more tiles than the stack holds. Whoever removes the very last tile wins.

Both players see the whole stack and play as well as the position allows. Return true if you can win from this stack no matter how your opponent replies, and false if your opponent can win no matter how you play.

Examples

Example 1

Input: count = 7
Output: true

You open by taking 3 tiles. Your opponent then takes 1, 2 or 3 of the 4 tiles left, and each of those replies leaves you a stack you clear on your next turn.

Example 2

Input: count = 96
Output: false

Whichever of 1, 2 or 3 tiles you open with, your opponent has a reply that keeps you from ever taking the last tile.

Example 3

Input: count = 3
Output: true

Taking 3 tiles is legal on a single turn, so you clear the stack immediately and the last tile is yours.

Constraints

1 <= count <= 2^31 - 1

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 can_take_last(count: int) -> bool:

Java

public boolean canTakeLast(int count)

The intended approach

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

Stacks split into winning and losing positions for the player about to move. A stack of size 0 is lost by the player to move, because the opponent has just taken the last tile. From a stack that is a multiple of four, every legal removal of 1, 2 or 3 tiles hands the opponent a stack that is not a multiple of four, and from any stack that is not a multiple of four the player to move can take 1, 2 or 3 tiles to hand back a multiple of four. So the answer is a single remainder test.

Pythonentry point: can_take_last

def can_take_last(count):
    # a stack whose size is a multiple of four leaves the player to move stuck:
    # whatever they take, 1, 2 or 3, the opponent can restore a multiple of four
    return count % 4 != 0

The obvious version

Fill in a table of who wins for every stack size up to a couple of hundred by minimax: a size is a win when at least one legal removal leads to a size that is a loss. Then find the shortest length after which that table repeats itself and read the answer for a huge stack off the repeating block, which keeps it usable past the table.

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_can_take_last(count):
    horizon = 200
    wins = [False] * (horizon + 1)
    for n in range(1, horizon + 1):
        wins[n] = any(not wins[n - take] for take in (1, 2, 3) if n - take >= 0)
    if count <= horizon:
        return wins[count]
    period = None
    for p in range(1, 41):
        if all(wins[i] == wins[i + p] for i in range(0, horizon - p + 1)):
            period = p
            break
    return wins[count % period]

How this problem was checked

Reference solution executed against 14 test cases — 14 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