0820MediumArrayMathGreedyMinimaxCountingGame TheoryNim GameZero-Sum Game

Crate Removal Duel

Tracked in this browser only

Trains the technique from

LeetCode 2029Stone Game IX

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 pallet holds a row of crates, and crate i weighs weights[i]. Two loaders, One and Two, empty the pallet in turns, and One always moves first.

On a turn the loader to move must take exactly one crate that is still on the pallet, any one of them, and put it on a shared heap. Straight after a crate lands on the heap, the total weight of every crate now on the heap is read off. If that total is divisible by 3, the loader who has just moved loses and the duel stops there.

If the pallet runs empty and neither loader has lost, Two wins.

Both loaders play as well as the position allows. Return true if One wins the duel, and false otherwise.

Examples

Example 1

Input: weights = [4, 8, 7]
Output: true

One opens by taking the crate of weight 8, so the heap weighs 8, which is not divisible by 3. Two must then take the crate of weight 4 or the crate of weight 7, bringing the heap to 12 or to 15, and both of those are divisible by 3.

Example 2

Input: weights = [6, 9, 12]
Output: false

One has to open with one of the three crates, leaving a heap of 6, 9 or 12, and every one of those totals is divisible by 3, so One loses on the opening move.

Example 3

Input: weights = [5, 11]
Output: false

Whichever crate One opens with, the heap holds 5 or 11 and the duel continues. Two then takes the remaining crate, bringing the heap to 16, which is not divisible by 3, and with the pallet empty and nobody having lost the win goes to Two.

Constraints

1 <= weights.length <= 10^5
1 <= weights[i] <= 10^4

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 first_player_wins(weights: list[int]) -> bool:

Java

public boolean firstPlayerWins(int[] weights)

The intended approach

Time O(n) for n crates: one pass to tally the remainders.Space O(1), three counters.

Two crates of the same weight remainder modulo 3 are interchangeable, so tally the crates into the three remainder classes. A crate from the class that is divisible by 3 leaves the heap total's remainder untouched and merely hands the turn over, so only the parity of that class matters. When it is even the duel is decided by whether both other classes are represented at all; when it is odd the turn order is inverted once and the decision comes down to how far apart the sizes of the other two classes are.

Pythonentry point: first_player_wins

def first_player_wins(weights):
    # Only each weight's remainder modulo 3 can affect the running heap total, so
    # the whole pallet reduces to three counts. A crate whose remainder is 0 never
    # changes the total's remainder, it only passes the turn, so what matters about
    # those crates is how many there are modulo 2. The other two classes have to
    # alternate for the total to stay clear of a multiple of 3, which is why the
    # answer only looks at whether both are present, or how far apart they are.
    # Time: O(n) for n crates.
    # Space: O(1).
    counts = [0, 0, 0]
    for w in weights:
        counts[w % 3] += 1
    if counts[0] % 2 == 0:
        return counts[1] >= 1 and counts[2] >= 1
    gap = counts[1] - counts[2]
    if gap < 0:
        gap = -gap
    return gap > 2

The obvious version

Solve the whole game outright. Crates sharing a weight remainder are interchangeable, so a position is the three remaining counts plus the heap total modulo 3 plus whose turn it is. Positions are filled in bottom up from those with fewer crates remaining, the loader to move taking any winning option and the empty pallet scoring for Two.

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_first_player_wins(weights):
    """Exhaustive game search. Crates with the same remainder are interchangeable,
    so a position is the three remaining counts, the heap total modulo 3 and whose
    turn it is; every position is filled in from positions with fewer crates left,
    bottom up, so no recursion is involved."""
    counts = [0, 0, 0]
    for w in weights:
        counts[w % 3] += 1
    a, b, c = counts
    span_c = c + 1
    span_b = b + 1

    def at(i, j, k, m, turn):
        return (((i * span_b + j) * span_c + k) * 3 + m) * 2 + turn

    # dp[state] is True when loader One eventually wins from that position
    dp = [False] * ((a + 1) * span_b * span_c * 6)
    for i in range(a + 1):
        for j in range(span_b):
            for k in range(span_c):
                if i == 0 and j == 0 and k == 0:
                    continue          # pallet empty: loader Two wins
                moves = []
                if i:
                    moves.append((0, i - 1, j, k))
                if j:
                    moves.append((1, i, j - 1, k))
                if k:
                    moves.append((2, i, j, k - 1))
                for m in range(3):
                    one_wins = False
                    for r, ni, nj, nk in moves:
                        nm = (m + r) % 3
                        if nm == 0:
                            continue   # One would lose on the spot
                        if dp[at(ni, nj, nk, nm, 1)]:
                            one_wins = True
                            break
                    dp[at(i, j, k, m, 0)] = one_wins
                    two_stuck = True
                    for r, ni, nj, nk in moves:
                        nm = (m + r) % 3
                        if nm == 0:
                            continue   # Two would lose on the spot, fine for One
                        if not dp[at(ni, nj, nk, nm, 0)]:
                            two_stuck = False
                            break
                    dp[at(i, j, k, m, 1)] = two_stuck
    return dp[at(a, b, c, 0, 0)]

How this problem was checked

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