Watch 10 video solutions for Minimum Operations to Halve Array Sum, a medium level problem involving Array, Greedy, Heap (Priority Queue). This walkthrough by Bro Coders has 1,479 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 the minimum number of operations to reduce the sum of nums by at least half.
Example 1:
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:
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 <= 1051 <= nums[i] <= 107Problem Overview: You are given an array of positive numbers. In one operation, you can pick any element and replace it with half of its value. The goal is to reduce the total array sum to at least half of its original value using the minimum number of operations.
Approach 1: Use a Max-Heap for Efficient Reduction (O(n log n) time, O(n) space)
The key observation: halving the largest element always produces the biggest decrease in the total sum. That makes this a natural fit for a greedy strategy. Start by computing the original array sum and push all elements into a max-heap. Repeatedly extract the largest value, halve it, subtract the reduction from the running sum, and push the halved value back into the heap.
A heap (priority queue) ensures you always access the current largest value in O(log n) time. Continue this process until the reduced amount reaches at least half of the original sum. Each operation maximizes the immediate reduction, which guarantees the minimum number of steps.
This approach works well because values shrink rapidly as they are halved. Even large inputs require relatively few heap operations in practice.
Approach 2: Greedy Reduction with Priority Queue (O(n log n) time, O(n) space)
This variation uses the same greedy insight but focuses on tracking how much reduction has been achieved instead of recomputing the entire sum repeatedly. First compute the total array sum and determine the target reduction: originalSum / 2. Insert every number into a max-priority queue.
Each iteration removes the current maximum, halves it, and adds the difference (the reduction) to a running counter. The halved value is pushed back into the queue because it may still be among the largest elements in future operations. Continue until the accumulated reduction reaches the target.
This formulation simplifies reasoning about the stopping condition and avoids recalculating sums. The algorithm still performs heap push and pop operations for every step, so the overall complexity remains O(n log n). The input structure itself is simply an array, but the heap drives the efficiency.
Recommended for interviews: The max-heap greedy approach is what interviewers expect. A brute-force idea (repeatedly scanning the array to find the largest element) demonstrates the greedy intuition but runs in O(n * k) time and does not scale. Using a heap shows you understand how to optimize repeated maximum selection to O(log n), which is the standard interview solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Scan for Largest (Brute Force) | O(n * k) | O(1) | Conceptual understanding or very small arrays |
| Greedy Max-Heap / Priority Queue | O(n log n) | O(n) | General case; optimal approach for interviews and large inputs |