Minimum limit of balls in a bag

Array Binary Search

66.5% acceptance

Feb 25, 2026

2835

105

You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations. You can perform the following operation at most maxOperations times: Take any bag of balls and divide it into two new bags with a positive number of balls. Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations. Return the minimum possible penalty after performing the operations.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_size(nums: Vec<i32>, max_operations: i32) -> i32 {
    let mut lo = 1i32;
    let mut hi = *nums.iter().max().unwrap();
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      // Operations needed to make all bags <= mid
      let ops: i64 = nums.iter().map(|&n| ((n - 1) / mid) as i64).sum();
      if ops <= max_operations as i64 {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}