Removing minimum number of magic beans

Array Greedy Sorting Enumeration Prefix Sum

44.4% acceptance

Feb 25, 2026

939

You are given an array beans where beans[i] is the number of magic beans in a magic bag. Remove any number of beans from each bag so all non-empty bags have equal beans. Return the minimum number of magic beans to remove.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_removal(beans: Vec<i32>) -> i64 {
    let mut beans = beans;
    beans.sort_unstable();
    let n = beans.len();
    let total: i64 = beans.iter().map(|&b| b as i64).sum();
    // For each index i, set target = beans[i]:
    // - all bags at index < i are emptied (their beans removed)
    // - all bags at index >= i are set to beans[i] (remove excess)
    // cost = total - beans[i] * (n - i)
    (0..n)
      .map(|i| total - beans[i] as i64 * (n - i) as i64)
      .min()
      .unwrap()
  }
}