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.
In this approach, we use a max-heap (priority queue) to always select the largest number for reduction, thus maximizing the decrease in the array's sum. This method ensures we use the smallest number of operations to achieve at least half reduction in the sum.
We begin by converting the given list into a max-heap, which allows us to efficiently retrieve and reduce the largest number. We then repeatedly take the largest number, halve it, and update our accumulated reductions until they account for at least half of the original sum. This approach optimally reduces the sum in the fewest operations possible by always selecting the largest available number for reduction.
Time Complexity: O(n log n), where n is the length of nums due to heap operations. Space Complexity: O(n) for the heap.
This approach also utilizes a priority queue to greedily select the largest number for halving. The goal is to minimize the operations by targeting the largest contributors to the sum first, therefore reducing the sum at a faster rate.
In this Java implementation, a priority queue is used to continuously select the largest number and halve it. By focusing on reducing the largest numbers, the process quickly lowers the total sum with minimal operations. The priority queue facilitates efficient retrieval and management of the largest elements.
Java
JavaScript
Time Complexity: O(n log n), due to priority queue operations. Space Complexity: O(n), for storing the elements in the priority queue.
According to the problem description, each operation will halve a number in the array. To minimize the number of operations that reduce the array sum by at least half, each operation should halve the current maximum value in the array.
Therefore, we first calculate the total sum s that the array needs to reduce, and then use a priority queue (max heap) to maintain all the numbers in the array. Each time we take the maximum value t from the priority queue, halve it, and then put the halved number back into the priority queue, while updating s, until s \le 0. The number of operations at this time is the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array.
| Approach | Complexity |
|---|---|
| Approach 1: Use a Max-Heap for Efficient Reduction | Time Complexity: O(n log n), where n is the length of |
| Approach 2: Greedy Reduction with Priority Queue | Time Complexity: O(n log n), due to priority queue operations. Space Complexity: O(n), for storing the elements in the priority queue. |
| Greedy + Priority Queue (Max Heap) | — |
| 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 |
2208. Minimum Operations to Halve Array Sum || Biweekly Contest 74 || Leetcode 2208 • Bro Coders • 1,479 views views
Watch 9 more video solutions →Practice Minimum Operations to Halve Array Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor