Problem

You are given an array nums of positive integers. In one operation, you can choose any number from nums and reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return _theminimum number of operations to reduce the sum of _nums byat least half.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: nums = [5,19,8,1]
Output: 3
Explanation: The initial sum of nums is equal to 5 + 19 + 8 + 1 = 33.
The following is one of the ways to reduce the sum by at least half:
Pick the number 19 and reduce it to 9.5.
Pick the number 9.5 and reduce it to 4.75.
Pick the number 8 and reduce it to 4.
The final array is [5, 4.75, 4, 1] with a total sum of 5 + 4.75 + 4 + 1 = 14.75. 
The sum of nums has been reduced by 33 - 14.75 = 18.25, which is at least half of the initial sum, 18.25 >= 33/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: nums = [3,8,20]
Output: 3
Explanation: The initial sum of nums is equal to 3 + 8 + 20 = 31.
The following is one of the ways to reduce the sum by at least half:
Pick the number 20 and reduce it to 10.
Pick the number 10 and reduce it to 5.
Pick the number 3 and reduce it to 1.5.
The final array is [1.5, 8, 5] with a total sum of 1.5 + 8 + 5 = 14.5. 
The sum of nums has been reduced by 31 - 14.5 = 16.5, which is at least half of the initial sum, 16.5 >= 31/2 = 15.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.

Constraints

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

Solution

Method 1 – Greedy & Max Heap

Intuition

To reduce the sum by at least half in minimum steps, always halve the largest number available. This greedy approach ensures the biggest reduction per operation.

Approach

  1. Calculate the initial sum and target (half of sum).
  2. Use a max heap to always pick the largest number.
  3. In each operation, halve the largest number, subtract the reduction from the remaining sum, and push the halved value back into the heap.
  4. Repeat until the sum is reduced by at least half.
  5. Count the number of operations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> pq;
        double sum = 0;
        for (int v : nums) {
            sum += v;
            pq.push(v);
        }
        double target = sum / 2, curr = sum;
        int ans = 0;
        while (curr > target) {
            double x = pq.top(); pq.pop();
            curr -= x / 2;
            pq.push(x / 2);
            ++ans;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import "container/heap"
type MaxHeap []float64
func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(float64)) }
func (h *MaxHeap) Pop() interface{}   { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func halveArray(nums []int) int {
    sum := 0.0
    h := &MaxHeap{}
    for _, v := range nums {
        sum += float64(v)
        heap.Push(h, float64(v))
    }
    target := sum / 2
    ans := 0
    for sum > target {
        x := heap.Pop(h).(float64)
        sum -= x / 2
        heap.Push(h, x/2)
        ans++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;
class Solution {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> pq = new PriorityQueue<>(Collections.reverseOrder());
        double sum = 0;
        for (int v : nums) {
            sum += v;
            pq.add((double)v);
        }
        double target = sum / 2;
        int ans = 0;
        while (sum > target) {
            double x = pq.poll();
            sum -= x / 2;
            pq.add(x / 2);
            ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.PriorityQueue
class Solution {
    fun halveArray(nums: IntArray): Int {
        val pq = PriorityQueue<Double>(compareByDescending { it })
        var sum = 0.0
        for (v in nums) {
            sum += v
            pq.add(v.toDouble())
        }
        val target = sum / 2
        var ans = 0
        while (sum > target) {
            val x = pq.poll()
            sum -= x / 2
            pq.add(x / 2)
            ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import heapq
class Solution:
    def halveArray(self, nums: list[int]) -> int:
        h = [-float(x) for x in nums]
        heapq.heapify(h)
        total: float = sum(nums)
        target: float = total / 2
        ans: int = 0
        curr: float = total
        while curr > target:
            x: float = -heapq.heappop(h)
            curr -= x / 2
            heapq.heappush(h, -x / 2)
            ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::BinaryHeap;
impl Solution {
    pub fn halve_array(nums: Vec<i32>) -> i32 {
        let mut pq = BinaryHeap::new();
        let mut sum = 0.0;
        for v in nums {
            sum += v as f64;
            pq.push(v as f64);
        }
        let target = sum / 2.0;
        let mut ans = 0;
        while sum > target {
            let x = pq.pop().unwrap();
            sum -= x / 2.0;
            pq.push(x / 2.0);
            ans += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    halveArray(nums: number[]): number {
        const h: number[] = [...nums].map(x => -x);
        h.sort((a, b) => a - b);
        let total = nums.reduce((a, b) => a + b, 0);
        let target = total / 2;
        let ans = 0;
        let curr = total;
        while (curr > target) {
            h.sort((a, b) => a - b);
            const x = -h.shift()!;
            curr -= x / 2;
            h.push(-(x / 2));
            ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n + k log n) — Building the heap is O(n log n), each operation is O(log n), k is number of operations.
  • 🧺 Space complexity: O(n) — For the heap.