Minimum Operations to Halve Array Sum

medium heap greedy

Problem

You are given an array of positive numbers. In one operation you may pick any element and replace it with exactly half of its value, removing the other half from the array's running sum. Return the minimum number of operations needed so that the total amount removed is at least half of the original sum.

Inputnums = [5, 19, 8, 1]

Output3

Original sum is 33, so we must remove at least 16.5. Halve 19 → remove 9.5; halve 9.5 → remove 4.75 (total 14.25); halve 8 → remove 4 (total 18.25 ≥ 16.5). That is 3 operations.

nums (comma-separated)

import heapq
def halve_array(nums):
    heap = [-float(x) for x in nums]
    heapq.heapify(heap)
    target = -sum(heap) / 2
    removed, ops = 0.0, 0
    while removed < target:
        x = -heapq.heappop(heap)
        removed += x / 2
        heapq.heappush(heap, -x / 2)
        ops += 1
    return ops

function halveArray(nums) {
  const heap = nums.map(Number);
  heap.sort((a, b) => b - a);
  const target = heap.reduce((a, b) => a + b, 0) / 2;
  let removed = 0, ops = 0;
  while (removed < target) {
    const x = heap.shift();
    removed += x / 2;
    insertDesc(heap, x / 2);
    ops += 1;
  }
  return ops;
}

class Solution {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> pq = new PriorityQueue<>(Collections.reverseOrder());
        double sum = 0;
        for (int x : nums) { pq.offer((double) x); sum += x; }
        double target = sum / 2, removed = 0;
        int ops = 0;
        while (removed < target) {
            double x = pq.poll();
            removed += x / 2;
            pq.offer(x / 2);
            ops++;
        }
        return ops;
    }
}

int halveArray(vector<int>& nums) {
    priority_queue<double> pq;
    double sum = 0;
    for (int x : nums) { pq.push((double) x); sum += x; }
    double target = sum / 2, removed = 0;
    int ops = 0;
    while (removed < target) {
        double x = pq.top(); pq.pop();
        removed += x / 2;
        pq.push(x / 2);
        ops++;
    }
    return ops;
}

Explanation

Every operation removes exactly half of whatever number you pick. To reach the target removal of sum / 2 in as few operations as possible, you want each operation to remove as much as it can. Since halving a number removes a chunk equal to half of that number, the biggest single removal always comes from halving the largest number currently present.

That is the greedy insight, and a max-heap makes it efficient: it always hands you the current maximum in O(log n). We push all numbers in, compute the goal target = sum / 2, then loop. Each round we pop the largest value x, add x / 2 to our running removed total, and push the halved value x / 2 back so it can compete again later.

We keep counting operations until removed reaches target, then return the count.

Example: nums = [5, 19, 8, 1], sum = 33, so target = 16.5. Pop 19, remove 9.5 (push 9.5). Pop 9.5, remove 4.75 for a total of 14.25 (push 4.75). Pop 8, remove 4 for a total of 18.25, which finally clears 16.5. Three operations.

Greedily attacking the largest available value each round guarantees the fastest possible climb toward the target, which is exactly the minimum number of operations.

Time: O(n log n) Space: O(n)