Minimum number of seconds to make mountain height zero

Array Math Binary Search Greedy Heap (Priority Queue)

36.9% acceptance

Feb 25, 2026

232

You are given an integer mountainHeight denoting the height of a mountain. You are also given an integer array workerTimes representing the work time of workers in seconds. Worker i reduces height by x in workerTimes[i] + workerTimes[i]*2 + ... + workerTimes[i]*x = workerTimes[i]*x*(x+1)/2 seconds. Workers work simultaneously. Return minimum number of seconds to reduce height to 0.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_number_of_seconds(mountain_height: i32, worker_times: Vec<i32>) -> i64 {
    // Binary search on time T.
    // For time T and worker i: max reduction x = largest x with workerTimes[i]*x*(x+1)/2 <= T
    // i.e., x*(x+1) <= 2T/workerTimes[i].
    // Solved via integer square root: x = isqrt(2T/w + 1/4) - 1/2
    //   = (isqrt(8T/w + 1) - 1) / 2  (integer arithmetic, avoids float precision)

    let h = mountain_height as i64;

    // Integer square root: largest x with x*x <= n
    let isqrt = |n: i64| -> i64 {
      if n <= 0 { return 0; }
      let mut x = (n as f64).sqrt() as i64;
      // One-step correction for float precision
      while x * x > n { x -= 1; }
      while (x + 1) * (x + 1) <= n { x += 1; }
      x
    };

    let max_reduction = |t: i64| -> i64 {
      worker_times.iter().map(|&w| {
        let w = w as i64;
        // x*(x+1) <= 2t/w  →  x = (isqrt(8t/w + 1) - 1) / 2
        let disc = 8 * t / w + 1;
        let x = ((isqrt(disc) - 1) / 2).min(h);
        x.max(0)
      }).sum()
    };

    // Upper bound: best worker (smallest workerTime) handles all h reductions alone.
    // Cost = min_w * h * (h+1) / 2 — tighter than using max_w, fewer binary search steps.
    let min_w = *worker_times.iter().min().unwrap() as i64;
    let mut lo = 0i64;
    let mut hi = min_w * h * (h + 1) / 2;

    while lo < hi {
      let mid = (lo + hi) / 2;
      if max_reduction(mid) >= h {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}