Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2208.html
2208. Minimum Operations to Halve Array Sum (Medium)
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 = 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.
Constraints:
1 <= nums.length <= 10^{5}
1 <= nums[i] <= 10^{7}
Similar Questions:
Solution 1. Heap
Greedily pick the greatest available number, half it and put it back, until the sum
halves. We can keep the available numbers in a MaxHeap for easy access to the max number.

// OJ: https://leetcode.com/problems/minimumoperationstohalvearraysum/ // Time: O(NlogN) // Space: O(N) class Solution { public: int halveArray(vector<int>& A) { priority_queue<double> pq; double sum = 0; int ans = 0; for (int n : A) { pq.push(n); sum += n; } double goal = sum / 2; while (sum > goal) { auto x = pq.top(); pq.pop(); sum = x / 2; pq.push(x / 2); ++ans; } return ans; } };

class Solution: def halveArray(self, nums: List[int]) > int: s = sum(nums) / 2 h = [] for v in nums: heappush(h, v) ans = 0 while s > 0: t = heappop(h) / 2 s = t heappush(h, t) ans += 1 return ans ############ # 2208. Minimum Operations to Halve Array Sum # https://leetcode.com/problems/minimumoperationstohalvearraysum/ class Solution: def halveArray(self, nums: List[int]) > int: total = sum(nums) target = total / 2 res = 0 pq = [x for x in nums] heapq.heapify(pq) while total > target: x = heapq.heappop(pq) x = (x) / 2 total = x res += 1 heapq.heappush(pq, x) return res

class Solution { public int halveArray(int[] nums) { long s = 0; PriorityQueue<Double> q = new PriorityQueue<>(Collections.reverseOrder()); for (int v : nums) { q.offer(v * 1.0); s += v; } double d = s / 2.0; int ans = 0; while (d > 0) { double t = q.poll(); d = t / 2.0; q.offer(t / 2.0); ++ans; } return ans; } }

func halveArray(nums []int) (ans int) { half := 0 for i := range nums { nums[i] <<= 20 half += nums[i] } h := hp{nums} heap.Init(&h) for half >>= 1; half > 0; ans++ { half = h.IntSlice[0] >> 1 h.IntSlice[0] >>= 1 heap.Fix(&h, 0) } return } type hp struct{ sort.IntSlice } func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] } func (hp) Push(interface{}) {} func (hp) Pop() (_ interface{}) { return }

function halveArray(nums: number[]): number { let s: number = nums.reduce((a, b) => a + b) / 2; const h = new MaxPriorityQueue(); for (const v of nums) { h.enqueue(v, v); } let ans: number = 0; while (s > 0) { let { element: t } = h.dequeue(); t /= 2; s = t; h.enqueue(t, t); ans += 1; } return ans; }
Discuss
https://leetcode.com/problems/minimumoperationstohalvearraysum/discuss/1863934/