0779HardArrayGreedy

Levelling The Grain Bins

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 mill has n grain bins standing in a row, and bins[i] is how many sacks bin i holds. Neighbouring bins are joined by a short conveyor; bin 0 and bin n - 1 each have a single neighbour, and the row does not wrap around.

The mill works in rounds. In one round you may choose any set of bins, and every chosen bin hands exactly one sack to one of its neighbours, either the one on its left or the one on its right. All the handovers of a round happen at the same time, so a bin may hand a sack away in the same round that it receives sacks, and a bin may receive from both sides at once. A bin can only hand over a sack it was already holding when the round began, and a bin holding no sacks cannot be chosen.

Return the least number of rounds after which every bin holds the same number of sacks, or -1 if no sequence of rounds can ever level the bins.

Examples

Example 1

Input: bins = [0,0,11,5]
Output: 8

The 16 sacks level out at 4 in every bin, and a run of 8 rounds gets them there.

Example 2

Input: bins = [0,12,0]
Output: 8

The 12 sacks level out at 4 in every bin, which is reached after 8 rounds.

Example 3

Input: bins = [7,0,4]
Output: -1

Eleven sacks cannot be shared evenly between three bins, so the bins can never end up level.

Example 4

Input: bins = [6,0,6]
Output: 2

The share is 4 each. In one round bin 0 hands a sack right and bin 2 hands a sack left at the same time, giving [5,2,5]; repeating that gives [4,4,4].

Constraints

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

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 find_min_moves(bins: list[int]) -> int:

Java

public int findMinMoves(int[] bins)

The intended approach

Time O(n): one pass over the bins after one pass to total them.Space O(1): only the running surplus and the best count so far.

If the total is not a multiple of `n` the bins can never level, so report `-1`. Otherwise sweep once from the left, keeping the running surplus of everything seen so far, which is the number of sacks that must be carried over the conveyor the sweep is standing on and therefore costs one round per sack. Track alongside it the surplus held by the current bin on its own, since that bin can only release one sack per round. The answer is the largest of those two quantities over the whole row.

Pythonentry point: find_min_moves

def find_min_moves(bins):
    # Every sack that has to cross the gap between bin i-1 and bin i crosses it in
    # its own round, and a bin can only hand out one sack per round, so track both
    # pressures in one sweep: the running surplus of the prefix, which is exactly
    # the traffic that must pass the current gap, and the surplus sitting in the
    # bin itself, which is what that single bin must ship out.
    # Time O(n), space O(1).
    n = len(bins)
    total = sum(bins)
    if total % n:
        return -1
    share = total // n
    rounds = 0
    running = 0
    for count in bins:
        running += count - share
        crossing = running if running >= 0 else -running
        if crossing > rounds:
            rounds = crossing
        if count - share > rounds:
            rounds = count - share
    return rounds

The obvious version

Breadth-first search over whole configurations. From a configuration, enumerate every combination of per-bin choices (hand left, hand right, stay put) that the rules allow and treat each combination as one round, stopping at the first level configuration. Exponential in the number of sacks, so it is only usable on tiny rows.

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

import itertools


def _round_moves(state):
    n = len(state)
    picks = []
    for i in range(n):
        opts = [0]
        if state[i] > 0:
            if i > 0:
                opts.append(-1)
            if i + 1 < n:
                opts.append(1)
        picks.append(opts)
    out = []
    for combo in itertools.product(*picks):
        nxt = list(state)
        for i, d in enumerate(combo):
            if d:
                nxt[i] -= 1
                nxt[i + d] += 1
        out.append(tuple(nxt))
    return out


def bf_find_min_moves(bins):
    n = len(bins)
    total = sum(bins)
    if total % n:
        return -1
    goal = tuple([total // n] * n)
    start = tuple(bins)
    if start == goal:
        return 0
    seen = {start}
    frontier = [start]
    rounds = 0
    while frontier:
        rounds += 1
        nxt = []
        for state in frontier:
            for cand in _round_moves(state):
                if cand == goal:
                    return rounds
                if cand not in seen:
                    seen.add(cand)
                    nxt.append(cand)
        frontier = nxt
    return -1

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
4 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