Minimum operations to halve array sum

Array Greedy Heap (Priority Queue)

50.0% acceptance

Feb 25, 2026

672

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Ordering;


#[derive(PartialEq)]
struct OrdF64(f64);
impl Eq for OrdF64 {}
impl PartialOrd for OrdF64 {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.0.partial_cmp(&other.0) }
}
impl Ord for OrdF64 {
  fn cmp(&self, other: &Self) -> Ordering { self.partial_cmp(other).unwrap_or(Ordering::Equal) }
}

impl Solution {
  pub fn halve_array(nums: Vec<i32>) -> i32 {
    let total: f64 = nums.iter().map(|&x| x as f64).sum();
    let target = total / 2.0;
    let mut heap: BinaryHeap<OrdF64> = nums.iter().map(|&x| OrdF64(x as f64)).collect();
    let mut reduced = 0.0f64;
    let mut ops = 0;
    while reduced < target {
      let top = heap.pop().unwrap().0;
      let half = top / 2.0;
      reduced += half;
      heap.push(OrdF64(half));
      ops += 1;
    }
    ops
  }
}