We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Halve Array Sum

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires a greedy approach to minimize the number of operations.
  • We can utilize a max heap (or priority queue) to always operate on the largest number available.
  • Each operation effectively reduces the current largest number, which maximizes the reduction in the overall sum.
  • The process continues until the total sum is reduced by at least half.

Space and Time Complexity

Time Complexity: O(n log n) - due to the heap operations for n elements. Space Complexity: O(n) - for storing the heap.

Solution

To solve this problem, we can use a max heap to keep track of the largest numbers. We repeatedly extract the maximum number from the heap, halve it, and push it back until the sum of the array is reduced by at least half. This greedy approach ensures that we're making the most impactful reductions first.

  1. Calculate the initial sum of the array.
  2. Create a max heap from the elements of the array.
  3. While the current sum is greater than half of the initial sum:
    • Extract the maximum value from the heap.
    • Halve this value.
    • Add the halved value back to the heap.
    • Update the current sum and increment the operation count.
  4. Return the count of operations.

Code Solutions

import heapq

def minOperations(nums):
    total_sum = sum(nums)
    target = total_sum / 2
    max_heap = [-num for num in nums]  # Create a max heap with negative values
    heapq.heapify(max_heap)
    
    current_sum = total_sum
    operations = 0
    
    while current_sum > target:
        max_value = -heapq.heappop(max_heap)  # Get the largest value
        reduced_value = max_value / 2
        current_sum -= reduced_value  # Update the current sum
        heapq.heappush(max_heap, -reduced_value)  # Push back the halved value
        operations += 1
        
    return operations
← Back to All Questions