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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Halve Array Sum

Number: 2310

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Given an array of positive integers, the goal is to determine the minimum number of operations required to reduce the total sum of the array by at least half. In each operation, you can choose any number from the array and reduce it to exactly half its value. This reduced number can then be used again in future operations.

Key Insights

  • Use a greedy approach: always reducing the largest number will maximize the reduction in sum.
  • Use a max-heap data structure to quickly retrieve the current largest number.
  • Maintain a running total of the reduction achieved until it reaches or exceeds half of the initial sum.
  • Re-insert the reduced number back into the max-heap since it can be reduced further if needed.

Space and Time Complexity

Time Complexity: O(n + k log n), where n is the number of elements and k is the number of operations performed. In the worst case, k can be proportional to n. Space Complexity: O(n) for storing the numbers in the heap.

Solution

The solution begins by computing the total sum of the array and establishing the target reduction as at least half of this sum. By using a max-heap, we can always extract and operate on the maximum number, which maximizes the reduction per operation. After halving the maximum element, the new value is pushed back into the heap so that it can be reduced further if required. This process is repeated until the cumulative reduction meets or exceeds the target.

Code Solutions

import heapq

def halveArray(nums):
    # Calculate the total sum and half of that sum.
    total_sum = sum(nums)
    target = total_sum / 2
    current_reduction = 0
    operations = 0
    
    # Create a max-heap by inserting negative values.
    max_heap = [-num for num in nums]
    heapq.heapify(max_heap)
    
    # Continue until the current reduction is at least the target.
    while current_reduction < target:
        # Pop the largest element (note: stored as negative).
        largest = -heapq.heappop(max_heap)
        # Calculate the half of the largest element.
        half_val = largest / 2
        # Increase the reduction by the difference.
        current_reduction += largest - half_val
        # Push the halved value back into the heap (as negative).
        heapq.heappush(max_heap, -half_val)
        # Increment the operation count.
        operations += 1
    
    return operations

# Example usage:
print(halveArray([5,19,8,1]))  # Output: 3
← Back to All Questions