< Back





2208. Minimum Operations to Halve Array Sum

Given an array, we're asked to find the minimum number of operations to halve the sum of the array.
The operations we can conduct are to halve any number in the array. After halving said number, we
can add it back to the array.

We use a max-heap to maintain the greatest numbers at the top, these are our halving targets. After
halving, we subtract their amount from the half of the sum of the original array. We then push this
halved number back onto the heap for future processing, if necessary. We continue these operations
until the half sum we calculated is <= 0.

The solution is as follows:


  from heapq import *

  class Solution:
      def halveArray(self, nums: List[int]) -> int:
          end, ans = sum(nums) / 2, 0
          nums = [-num for num in nums]
          heapify(nums)

          while end > 0:
              num = -heappop(nums) / 2
              end -= num
              ans += 1
              heappush(nums, -num)

          return ans


_ Time Complexity:

  O(n log n) - We conduct at most n steps, and heap operations take at most log n time.

_ Space Complexity:

  O(n) - We store all the nums in the heap.