Minimum Operations to Halve Array Sum
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
3By repeatedly halving 19, then halving 8, the sum is reduced from 33 to 14.75, which is at least half of the initial sum, and this cannot be done in fewer than 3 operations.
Example 2
Input
nums = [3,8,20]Output
3By halving 20, then halving 10, then halving 3, the sum is reduced from 31 to 14.5, which is at least half of the initial sum, and this cannot be done in fewer than 3 operations.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^7