Minimum k to reduce array within limit

Array Binary Search

41.1% acceptance

Mar 16, 2026

For positive integer k, nonPositive(nums, k) = min operations to make all elements <= 0, where each operation subtracts k from one element. Return min k such that nonPositive(nums, k) <= k^2.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_k(nums: Vec<i32>) -> i32 {
    // For a given k, nonPositive = sum of ceil(nums[i] / k) for all i
    // We need sum(ceil(nums[i]/k)) <= k^2
    // Binary search on k
    let mut lo = 1i64;
    let mut hi = 100001i64;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      let ops: i64 = nums.iter().map(|&x| ((x as i64) + mid - 1) / mid).sum();
      if ops <= mid * mid {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo as i32
  }
}