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] <= 107In #2208 Minimum Operations to Halve Array Sum, the goal is to reduce the total array sum by at least half using the minimum number of operations. Each operation allows you to pick a number and replace it with half of its value. The key observation is that reducing the largest element always provides the greatest immediate decrease in the overall sum.
A greedy strategy works well here. Store all elements in a max heap (priority queue) so that the largest value can be accessed quickly. Track the current sum and the target (half of the original sum). Repeatedly remove the largest value from the heap, halve it, subtract the reduced portion from the running sum, and push the new value back into the heap. Continue until the total reduction reaches the required threshold.
Using a heap ensures efficient access to the maximum element each time. The process involves repeated heap operations, giving a time complexity of O(n log n) and space complexity of O(n).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Max Heap (Priority Queue) | O(n log n) | O(n) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
It is always optimal to halve the largest element.
What data structure allows for an efficient query of the maximum element?
Use a heap or priority queue to maintain the current elements.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A greedy strategy works because halving the largest number always maximizes the reduction in the total sum for that operation. By consistently choosing the element that gives the biggest decrease, the algorithm minimizes the total number of operations required.
Yes, variations of heap and greedy problems like this frequently appear in FAANG and other top tech company interviews. The problem tests understanding of priority queues, greedy decision making, and efficient simulation of repeated operations.
A max heap (priority queue) is the best data structure for this problem. It allows efficient retrieval and reinsertion of the largest element after halving it, ensuring each operation runs in logarithmic time.
The optimal approach uses a greedy strategy with a max heap (priority queue). At each step, you halve the largest element because it produces the maximum possible reduction in the total sum. This process continues until the array sum becomes at most half of the original sum.