Show problems as
Classic problem #2208MediumArrayGreedyHeap (Priority Queue)

Minimum Operations to Halve Array Sum

Real-world version: Halving the Load on a Rig
Tracked in this browser only
Read Minimum Operations to Halve Array Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def halve_array(nums: list[int]) -> int:
Java
public int halveArray(int[] nums)

More on the same topics