Minimum operations to make numbers non positive

Array Binary Search

44.1% acceptance

Mar 31, 2026

You are given a 0-indexed integer array nums and two integers x and y. In one operation, you must choose an index i such that 0 <= i < nums.length and perform the following: Decrement nums[i] by x. Decrement values by y at all indices except the ith one. Return the minimum number of operations to make all the integers in nums less than or equal to zero.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums: Vec<i32>, x: i32, y: i32) -> i32 {
    let x = x as i64;
    let y = y as i64;
    let check = |ops: i64| -> bool {
      let mut total: i64 = 0;
      for &v in &nums {
        let rem = v as i64 - y * ops;
        if rem > 0 {
          total += (rem + x - y - 1) / (x - y);
          if total > ops { return false; }
        }
      }
      total <= ops
    };
    let mut lo: i64 = 0;
    let mut hi: i64 = 1_000_000_000;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if check(mid) { hi = mid; } else { lo = mid + 1; }
    }
    lo as i32
  }
}