2208. Minimum Operations to Halve Array Sum LeetCode Solution

In this guide, you will get 2208. Minimum Operations to Halve Array Sum LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Halve Array Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Operations to Halve Array Sum solution in C++
Minimum Operations to Halve Array Sum solution in Java
Minimum Operations to Halve Array Sum solution in Python
Additional Resources

2208. Minimum Operations to Halve Array Sum LeetCode Solution image

Problem Statement of Minimum Operations to Halve Array Sum

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.

Complexity Analysis

Time Complexity: O(n\log n + k\log n),, k = # of operations
Space Complexity: O(n)

2208. Minimum Operations to Halve Array Sum LeetCode Solution in C++

class Solution {
 public:
  int halveArray(vector<int>& nums) {
    const double halfSum = accumulate(nums.begin(), nums.end(), 0.) / 2;
    int ans = 0;
    double runningSum = 0;
    priority_queue<double> maxHeap{nums.begin(), nums.end()};

    while (runningSum < halfSum) {
      const double maxValue = maxHeap.top() / 2;
      runningSum += maxValue, maxHeap.pop();
      maxHeap.push(maxValue);
      ++ans;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2208. Minimum Operations to Halve Array Sum LeetCode Solution in Java

class Solution {
  public int halveArray(int[] nums) {
    final double halfSum = Arrays.stream(nums).asDoubleStream().sum() / 2;
    int ans = 0;
    double runningSum = 0;
    Queue<Double> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    for (final double num : nums)
      maxHeap.offer(num);

    while (runningSum < halfSum) {
      final double maxValue = maxHeap.poll() / 2;
      runningSum += maxValue;
      maxHeap.offer(maxValue);
      ++ans;
    }

    return ans;
  }
}
// code provided by PROGIEZ

2208. Minimum Operations to Halve Array Sum LeetCode Solution in Python

class Solution:
  def halveArray(self, nums: list[int]) -> int:
    halfSum = sum(nums) / 2
    ans = 0
    runningSum = 0.0
    maxHeap = [-num for num in nums]

    heapq.heapify(maxHeap)

    while runningSum < halfSum:
      maxValue = -heapq.heappop(maxHeap) / 2
      runningSum += maxValue
      heapq.heappush(maxHeap, -maxValue)
      ans += 1

    return ans
 # code by PROGIEZ