Skip to main content
Talentd

Minimum Operations to Halve Array Sum - Solution & Explanation

MediumArrayGreedyHeap (Priority Queue)14 min readAsked at: Microsoft, Oracle
Practice this problem

Problem Statement

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 = 15.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 <= 105
  • 1 <= nums[i] <= 107

Approach Overview

Problem Overview: You are given an array of positive numbers. In one operation, you can pick any element and replace it with half of its value. The goal is to reduce the total array sum to at least half of its original value using the minimum number of operations.

Approach 1: Use a Max-Heap for Efficient Reduction (O(n log n) time, O(n) space)

The key observation: halving the largest element always produces the biggest decrease in the total sum. That makes this a natural fit for a greedy strategy. Start by computing the original array sum and push all elements into a max-heap. Repeatedly extract the largest value, halve it, subtract the reduction from the running sum, and push the halved value back into the heap.

A heap (priority queue) ensures you always access the current largest value in O(log n) time. Continue this process until the reduced amount reaches at least half of the original sum. Each operation maximizes the immediate reduction, which guarantees the minimum number of steps.

This approach works well because values shrink rapidly as they are halved. Even large inputs require relatively few heap operations in practice.

Approach 2: Greedy Reduction with Priority Queue (O(n log n) time, O(n) space)

This variation uses the same greedy insight but focuses on tracking how much reduction has been achieved instead of recomputing the entire sum repeatedly. First compute the total array sum and determine the target reduction: originalSum / 2. Insert every number into a max-priority queue.

Each iteration removes the current maximum, halves it, and adds the difference (the reduction) to a running counter. The halved value is pushed back into the queue because it may still be among the largest elements in future operations. Continue until the accumulated reduction reaches the target.

This formulation simplifies reasoning about the stopping condition and avoids recalculating sums. The algorithm still performs heap push and pop operations for every step, so the overall complexity remains O(n log n). The input structure itself is simply an array, but the heap drives the efficiency.

Recommended for interviews: The max-heap greedy approach is what interviewers expect. A brute-force idea (repeatedly scanning the array to find the largest element) demonstrates the greedy intuition but runs in O(n * k) time and does not scale. Using a heap shows you understand how to optimize repeated maximum selection to O(log n), which is the standard interview solution.

Approach 1: Approach 1: Use a Max-Heap for Efficient Reduction

In this approach, we use a max-heap (priority queue) to always select the largest number for reduction, thus maximizing the decrease in the array's sum. This method ensures we use the smallest number of operations to achieve at least half reduction in the sum.

We begin by converting the given list into a max-heap, which allows us to efficiently retrieve and reduce the largest number. We then repeatedly take the largest number, halve it, and update our accumulated reductions until they account for at least half of the original sum. This approach optimally reduces the sum in the fewest operations possible by always selecting the largest available number for reduction.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n log n), where n is the length of nums due to heap operations. Space Complexity: O(n) for the heap.

Try this approach in the editor →

Approach 2: Approach 2: Greedy Reduction with Priority Queue

This approach also utilizes a priority queue to greedily select the largest number for halving. The goal is to minimize the operations by targeting the largest contributors to the sum first, therefore reducing the sum at a faster rate.

In this Java implementation, a priority queue is used to continuously select the largest number and halve it. By focusing on reducing the largest numbers, the process quickly lowers the total sum with minimal operations. The priority queue facilitates efficient retrieval and management of the largest elements.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n log n), due to priority queue operations. Space Complexity: O(n), for storing the elements in the priority queue.

Try this approach in the editor →

Approach 3: Greedy + Priority Queue (Max Heap)

According to the problem description, each operation will halve a number in the array. To minimize the number of operations that reduce the array sum by at least half, each operation should halve the current maximum value in the array.

Therefore, we first calculate the total sum s that the array needs to reduce, and then use a priority queue (max heap) to maintain all the numbers in the array. Each time we take the maximum value t from the priority queue, halve it, and then put the halved number back into the priority queue, while updating s, until s \le 0. The number of operations at this time is the answer.

The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Use a Max-Heap for Efficient Reduction

Time Complexity: O(n log n), where n is the length of nums due to heap operations. Space Complexity: O(n) for the heap.

Approach 2: Greedy Reduction with Priority Queue

Time Complexity: O(n log n), due to priority queue operations. Space Complexity: O(n), for storing the elements in the priority queue.

Greedy + Priority Queue (Max Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Scan for Largest (Brute Force)O(n * k)O(1)Conceptual understanding or very small arrays
Greedy Max-Heap / Priority QueueO(n log n)O(n)General case; optimal approach for interviews and large inputs

Video Solution

2208. Minimum Operations to Halve Array Sum || Biweekly Contest 74 || Leetcode 2208 • Bro Coders • 1,506 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Halve Array Sum easy or hard?
The problem is rated Medium because the greedy insight is not immediately obvious. Once you recognize that halving the largest number always maximizes the reduction, the rest of the solution becomes straightforward using a heap. Implementation is simple but recognizing the greedy strategy is the main challenge.
Minimum Operations to Halve Array Sum Python/Java solution
Python solutions typically use the heapq module with negative values to simulate a max-heap. Java implementations use PriorityQueue with a custom comparator for descending order. Both follow the same greedy process: repeatedly halve the largest element until the sum is reduced by at least half.
How to solve Minimum Operations to Halve Array Sum in O(n)?
A strict O(n) solution is not practical because the algorithm repeatedly needs the current maximum element after updates. Without a heap or priority queue, finding the maximum would require scanning the array each time. Using a max-heap reduces this to O(log n) per operation, giving an overall O(n log n) complexity which is considered optimal.
What is the best approach for Minimum Operations to Halve Array Sum?
The optimal approach uses a greedy strategy with a max-heap (priority queue). Always halve the largest number because it produces the greatest reduction in the total sum. Each operation removes the maximum value from the heap, halves it, and pushes the result back. This guarantees the minimum number of operations with O(n log n) time complexity.
Is Minimum Operations to Halve Array Sum asked at Google/Amazon/Meta?
Greedy problems combined with heaps appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests the ability to identify a greedy choice and implement it efficiently with a priority queue, a common interview pattern for optimization problems.
What data structure is used in Minimum Operations to Halve Array Sum?
A max-heap (implemented using a priority queue) is the primary data structure. It allows constant access to the largest value and supports efficient updates when values are halved and pushed back into the structure.
What is the time complexity of Minimum Operations to Halve Array Sum?
The optimal heap-based solution runs in O(n log n) time. Building the max-heap takes O(n), and each operation requires a pop and push operation that costs O(log n). The space complexity is O(n) for storing elements inside the priority queue.

Ready to solve this problem?

Practice Minimum Operations to Halve Array Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Exceed Threshold Value II

Next

Remove Stones to Minimize the Total