Ctrl K

Snowball Swallows Everything

Medium
A snowball weighing size rolls across a field of snowdrifts whose weights are given in drifts. You choose the order in which it hits the drifts. If the snowball weighs at least as much as a drift, it absorbs the drift and gains its weight. If the drift is heavier, the snowball falls apart. Return True if the snowball can pick up every drift, and False otherwise.
Example 1
size=5, drifts=[12, 3, 6, 1] → True

Take them as 1, 3, 6, 12: the snowball grows 5 → 6 → 9 → 15 → 27 and picks up everything.

Example 2
size=2, drifts=[3, 1, 9] → False

After drifts 1 and 3 the snowball weighs 6, and the drift of 9 is heavier: no order gets past it.

Constraints
  • 1 ≤ size ≤ 10⁵
  • 1 ≤ len(drifts) ≤ 10⁵
  • 1 ≤ drifts[i] ≤ 10⁵
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsBiggest Number From Pieces MediumStudios for Recording Sessions MediumLow, High, Low MediumStrictly Low, High, Low MediumFewest Meetings to Cancel Medium
loading Python…
Input
size=5, drifts=[12, 3, 6, 1]
Expected
True

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.