0893MediumArrayGreedySorting

Snowball Down the Slope

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 snowball of weight mass is set rolling past a line of clumps whose weights are given as asteroids. The clumps may be taken in any order you like.

The snowball takes a clump only when its own weight is at least that clump's weight, and taking it adds the clump's weight to the snowball. Meeting a clump heavier than the snowball ends the run.

Return true when some order lets the snowball take every clump.

Examples

Example 1

Input: mass = 17, asteroids = [23, 9, 41, 5, 62]
Output: true

Going lightest first, the snowball reaches 22, then 31, then 54, then 95, then 157, and nothing was ever too heavy for it.

Example 2

Input: mass = 2, asteroids = [1, 4, 9]
Output: false

Taking the 1 first brings the snowball to 3, which is not enough for the 4, so the run cannot be completed. Note that with a 4 it would have reached 7 and then managed the 9, so the order matters.

Example 3

Input: mass = 4, asteroids = [4, 8, 16, 32, 64]
Output: true

Each clump exactly matches the weight the snowball has reached, and matching is enough, so it doubles its way through all five.

Constraints

1 <= mass <= 10^5
1 <= asteroids.length <= 10^5
1 <= asteroids[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 asteroids_destroyed(mass: int, asteroids: list[int]) -> bool:

Java

public boolean asteroidsDestroyed(int mass, int[] asteroids)

The intended approach

Time O(n log n) for n clumps, the sort being the cost.Space O(n) for the sorted order, or O(1) if the input may be sorted in place.

Taking a clump only ever makes the snowball heavier, so no order can be worse off for having taken something earlier. That means the lightest clump available is always safe to take first: if any order succeeds, the one that goes lightest-first does too, since at every point it has taken at least as much weight as the other order had. So sort the clumps and roll through them, adding each to the running weight, and report failure the moment one is too heavy.

Pythonentry point: asteroids_destroyed

def asteroids_destroyed(mass, asteroids):
    weight = mass
    for clump in sorted(asteroids):
        if weight < clump:
            return False
        weight += clump
    return True

The obvious version

Try every order of the clumps and report success if any order gets through. Factorial in the clump count and it assumes nothing about which order is worth trying.

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_asteroids_destroyed(mass, asteroids):
    import itertools
    for order in itertools.permutations(asteroids):
        weight = mass
        ok = True
        for clump in order:
            if weight < clump:
                ok = False
                break
            weight += clump
        if ok:
            return True
    return False

How this problem was checked

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