# Minimum Operations to Halve Array Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-halve-array-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-halve-array-sum
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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`

# Approaches
## Brute Force with Repeated Linear Scan
This approach follows a greedy strategy. To minimize the number of operations, we should always aim to reduce the sum by the largest possible amount in each step. The reduction from halving a number `x` is `x/2`. Therefore, to get the maximum reduction, we should always pick the largest number in the current array and halve it.

This approach implements the greedy strategy in a straightforward way. In each step, it iterates through the entire array to find the maximum element, halves it, and updates the sum. This process is repeated until the total sum is reduced by at least half.
**Time:** O(k * n)
Let `n` be the number of elements in the array and `k` be the number of operations performed. In each operation, we scan the entire array to find the maximum element, which takes O(n) time. Since this is done `k` times, the total time complexity is O(k * n). In the worst case, this can be too slow if both `n` and `k` are large. · **Space:** O(n)
We create a `double` array of size `n` to store the numbers, as they can become non-integers. If we are allowed to modify the input array and can cast it, we could potentially achieve O(1) space, but using a separate `double` array is safer and cleaner.
**Pros:** Simple to understand and implement.; Correctly implements the greedy logic.
**Cons:** Inefficient due to the repeated linear scan to find the maximum element.; Likely to result in a "Time Limit Exceeded" error on large test cases.
### Explanation
The algorithm proceeds as follows:
1.  First, calculate the initial sum of all numbers in the `nums` array. Let's call this `initialSum`.
2.  The goal is to reduce the sum by at least `initialSum / 2`. This means the current sum of the array must become less than or equal to `initialSum / 2`. Let's define `targetSum = initialSum / 2`.
3.  We also need to keep track of the `currentSum` of the array elements. Initially, `currentSum` is equal to `initialSum`.
4.  We use a loop that continues as long as `currentSum > targetSum`. Inside the loop:
    a. We find the largest number in the array and its index. This requires a full scan of the array.
    b. We take this largest number, say `maxVal`, and calculate the amount it will be reduced by, which is `reduction = maxVal / 2`.
    c. We update the element in the array to its new halved value.
    d. We decrease the `currentSum` by the `reduction` amount.
    e. We increment a counter for the number of operations.
5.  Once the loop terminates (i.e., `currentSum <= targetSum`), the value of the operations counter is the minimum number of operations required.

Since we are dealing with potentially non-integer values after halving, it's best to use floating-point numbers (like `double`) for calculations involving the sum and array elements.

```java
import java.util.Arrays;

class Solution {
    public int halveArray(int[] nums) {
        // Use a double array to handle non-integer values after halving.
        double[] doubleNums = new double[nums.length];
        double initialSum = 0;
        for (int i = 0; i < nums.length; i++) {
            doubleNums[i] = (double) nums[i];
            initialSum += doubleNums[i];
        }

        double targetSum = initialSum / 2.0;
        double currentSum = initialSum;
        int operations = 0;

        while (currentSum > targetSum) {
            // Find the maximum element in the array
            int maxIndex = -1;
            double maxVal = -1.0;
            for (int i = 0; i < doubleNums.length; i++) {
                if (doubleNums[i] > maxVal) {
                    maxVal = doubleNums[i];
                    maxIndex = i;
                }
            }

            // Halve the maximum element
            double reduction = maxVal / 2.0;
            doubleNums[maxIndex] = reduction;
            
            // Update the current sum and operations count
            currentSum -= reduction;
            operations++;
        }

        return operations;
    }
}
```
### Algorithm
*   Calculate the initial sum `S` of the array.
*   Define the target sum `T = S / 2`.
*   Initialize `currentSum = S` and `operations = 0`.
*   Create a copy of the input array as a `double` array to handle floating-point numbers.
*   Start a loop that continues as long as `currentSum > T`.
    *   Iterate through the array to find the maximum value `maxVal` and its index `maxIdx`.
    *   Calculate the reduction amount: `reduction = maxVal / 2`.
    *   Update the array: `nums[maxIdx] -= reduction`.
    *   Update the sum: `currentSum -= reduction`.
    *   Increment the `operations` counter.
*   Return `operations`.

## Greedy Approach with a Max-Heap (Priority Queue)
This approach also uses the same greedy strategy: always halve the largest number to get the maximum possible reduction in sum. However, it optimizes the process of finding the largest number. Instead of scanning the array every time, we use a max-heap (implemented as a `PriorityQueue` in Java).

A max-heap is a data structure that allows us to efficiently retrieve the maximum element. By storing all the numbers in a max-heap, we can get the largest number in O(log n) time. After halving it, we insert the new, smaller number back into the heap, which also takes O(log n) time. This is significantly faster than the O(n) linear scan of the previous approach.
**Time:** O(n + k log n)
Let `n` be the number of elements and `k` be the number of operations.
- Calculating the initial sum takes O(n).
- Building the heap from `n` elements takes O(n) time.
- The loop runs `k` times. Inside the loop, `poll()` and `add()` operations on the heap each take O(log n) time.
- Thus, the total time complexity is O(n + k log n). This is much more efficient than the brute-force approach. · **Space:** O(n)
We need a heap to store all `n` numbers from the array. Therefore, the space complexity is O(n).
**Pros:** Highly efficient for the given constraints.; Correctly implements the greedy strategy in an optimized way.; The standard and best approach for this type of problem.
**Cons:** Requires extra space for the heap.; Slightly more complex to implement than the brute-force approach due to the use of a Priority Queue.
### Explanation
The core idea is to maintain the array elements in a data structure that provides fast access to the maximum element. A max-heap is perfect for this.

The algorithm is as follows:
1.  Calculate the `initialSum` of the elements in `nums`. We use `double` for precision.
2.  The target is to achieve a total reduction of at least `initialSum / 2`. Let's call this `reductionNeeded`.
3.  Create a max-heap (in Java, a `PriorityQueue` with a reverse order comparator) and populate it with all the numbers from the input array. Building the heap takes O(n) time.
4.  Initialize `operations = 0` and `sumReduced = 0.0`.
5.  Start a loop that continues as long as `sumReduced < reductionNeeded`.
    a. Extract the maximum element from the heap using `poll()`. This is an O(log n) operation. Let the element be `maxVal`.
    b. The reduction achieved in this step is `reduction = maxVal / 2`.
    c. Add this `reduction` to `sumReduced`.
    d. The new value of the element is `maxVal / 2`. Insert this new value back into the heap using `add()`. This is also an O(log n) operation.
    e. Increment the `operations` counter.
6.  Once `sumReduced` is greater than or equal to `reductionNeeded`, the loop terminates. The value of `operations` is the minimum required.

```java
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int halveArray(int[] nums) {
        // Use a PriorityQueue as a max-heap to store the numbers.
        // We need to use double for precision.
        PriorityQueue<Double> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        double initialSum = 0;
        for (int num : nums) {
            maxHeap.add((double) num);
            initialSum += num;
        }

        double targetReduction = initialSum / 2.0;
        double sumReduced = 0;
        int operations = 0;

        while (sumReduced < targetReduction) {
            // Get the largest number from the heap.
            double maxVal = maxHeap.poll();
            
            // Calculate the reduction and the new value.
            double reduction = maxVal / 2.0;
            
            // Update the total reduction and add the new value back to the heap.
            sumReduced += reduction;
            maxHeap.add(reduction); // The new value is the same as the reduction amount.
            
            // Increment the operation count.
            operations++;
        }

        return operations;
    }
}
```
### Algorithm
*   Calculate the initial sum `S` of the array.
*   Define the required reduction `R = S / 2`.
*   Create a max-heap (e.g., `PriorityQueue<Double>` with `Collections.reverseOrder()`).
*   Add all elements from `nums` into the max-heap.
*   Initialize `sumReduced = 0.0` and `operations = 0`.
*   Start a loop that continues as long as `sumReduced < R`.
    *   Extract the maximum element `maxVal` from the heap (`poll()`).
    *   Calculate the reduction: `reduction = maxVal / 2`.
    *   Update the total reduction: `sumReduced += reduction`.
    *   Insert the new value (`reduction`) back into the heap (`add()`).
    *   Increment the `operations` counter.
*   Return `operations`.

# Solutions
### Java

```java
class Solution { public int halveArray ( int [] nums ) { double s = 0 ; PriorityQueue < Double > q = new PriorityQueue <>( Collections . reverseOrder ()); for ( int v : nums ) { q . offer ( v * 1.0 ); s += v ; } s /= 2.0 ; int ans = 0 ; while ( s > 0 ) { double t = q . poll (); s -= t / 2.0 ; q . offer ( t / 2.0 ); ++ ans ; } return ans ; } }
```

### CPP

```cpp
class Solution { public: int halveArray ( vector < int >& nums ) { priority_queue < double > q ; double s = 0 ; for ( int & v : nums ) { s += v ; q . push ( v ); } s /= 2.0 ; int ans = 0 ; while ( s > 0 ) { double t = q . top () / 2 ; q . pop (); s -= t ; q . push ( t ); ++ ans ; } return ans ; } };
```

### Python

```python
class Solution : def halveArray ( self , nums : List [ int ]) -> int : s = sum ( nums ) / 2 h = [] for v in nums : heappush ( h , - v ) ans = 0 while s > 0 : t = - heappop ( h ) / 2 s -= t heappush ( h , - t ) ans += 1 return ans
```