0895MediumArrayGreedyHeap (Priority Queue)

Halving the Load on a Rig

Tracked in this browser only

Trains the technique from

LeetCode 2208Minimum Operations to Halve Array Sum

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 rig carries loads given as nums. One easing picks any load and replaces it with exactly half of it, which may leave a fraction.

Return the fewest easings that bring the total of the loads down to at most half of what it started at.

Examples

Example 1

Input: nums = [19, 6, 33, 12]
Output: 4

The loads total 70, so 35 has to come off. Easing 33 sheds 16.5, easing the 19 sheds 9.5, easing the 16.5 sheds 8.25, and that already covers 34.25; one more easing carries it past 35.

Example 2

Input: nums = [2, 2]
Output: 2

The total is 4 and 2 has to come off. One easing sheds only 1, so a second is needed, and reaching exactly half is enough.

Example 3

Input: nums = [10000000]
Output: 1

A single easing halves the only load, which is exactly half the total.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^7

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 halve_array(nums: list[int]) -> int:

Java

public int halveArray(int[] nums)

The intended approach

Time O(n + k log n) for n loads and k easings: building the heap is linear and each easing costs a heap step.Space O(n) for the heap.

Each easing removes exactly half of whatever load it lands on, so an easing spent on the largest load available always removes the most weight that any single easing could. Spending easings in that order is optimal by an exchange argument: swapping any easing for one on a heavier load never removes less, and the loads only ever shrink, so nothing later is made worse. That makes the method a heap of the loads, largest at the top: take the top, halve it, add what was shed to a running tally, and push the half back. Stop as soon as the tally covers half the starting total. Halving is exact in binary, so scaling every load once by a power of two and halving with a shift keeps the whole thing in whole numbers and leaves no rounding to worry about.

Pythonentry point: halve_array

def halve_array(nums):
    import heapq
    scale = 64
    heap = [-(v << scale) for v in nums]
    heapq.heapify(heap)
    total = 0
    for v in nums:
        total += v << scale
    shed = 0
    steps = 0
    while shed * 2 < total:
        top = -heapq.heappop(heap)
        half = top >> 1
        shed += top - half
        heapq.heappush(heap, -half)
        steps += 1
    return steps

The obvious version

Order does not change where the loads end up, only how many easings each load received, so try every way of handing out one easing, then two, then three, and so on, and stop at the first count that works. Grows very fast with the count and it never argues about which load to ease.

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_halve_array(nums):
    n = len(nums)
    scale = 64
    scaled = [v << scale for v in nums]
    total = 0
    for v in scaled:
        total += v

    def enough(share):
        left = 0
        for i in range(n):
            left += scaled[i] >> share[i]
        return (total - left) * 2 >= total

    def hand_out(at, budget, share):
        if at == n - 1:
            share[at] = budget
            return enough(share)
        for give in range(budget + 1):
            share[at] = give
            if hand_out(at + 1, budget - give, share):
                return True
        share[at] = 0
        return False

    count = 0
    while True:
        if hand_out(0, count, [0] * n):
            return count
        count += 1

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