Minimum operations to halve array sum

October 19, 2022


Problem URL: Minimum operations to halve array sum

We will compute the half of the sum of the input nums, put all nums into a max heap. Then pull out and cut the current max value by half and add it back to heap, deduct the half of the sum accordingly and increase the counter ops by 1. Repeat it utill half <= 0, then return ops.

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

        while half > 0:
            num = -heapq.heappop(heap)
            num /= 2.0
            half -= num
            heappush(heap, -num)
            ops += 1

        return ops

Time Complexity: O(nlog(n))
Space Complexity: O(n)