LeetCode Entry

3296. Minimum Number of Seconds to Make Mountain Height Zero

13.03.2026 medium 2026 kotlin rust

Min steps to work a mountain with arithmetic-sum-workers

3296. Minimum Number of Seconds to Make Mountain Height Zero medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1296

Problem TLDR

Min steps to work a mountain with arithmetic-sum-workers #medium #bs

Intuition

    // the description is brainrot
    // 1+2+3+4+5 + (n-2)+(n-1)+n = s
    //

Binary search: freeze the number of parallel steps, test the amount of total work done. Inner binary search to answer what number of steps is the maximum allowed to be less than frozen steps.

Approach

• S = x*(x+1)/2
• there is a math solution possible for inner bs
• live math in rust is slower than precomputed array in kotlin

Complexity

• Time complexity: \(O(log(nlog(w)))\)

• Space complexity: \(O(w)\) can be O(1)

Code

// 117ms
    fun minNumberOfSeconds(mh: Int, wt: IntArray): Long {
        val a = LongArray(mh+1) { 1L * it * (it+1)/2 }
        var lo = 0L; var hi = 1L shl 62
        while (lo <= hi) {
            val m = lo + (hi - lo) / 2
            if (mh > wt.sumOf { t ->
                var i = a.binarySearch(m/t); if (i < 0) i = -i-2; i
            }) lo = m + 1 else hi = m - 1
        }
        return lo
    }

// 144ms
    pub fn min_number_of_seconds(mh: i32, wt: Vec<i32>) -> i64 {
        let (mut lo, mut hi) = (0i64, 1i64<<62);
        while lo <= hi {
            let m = lo + (hi - lo) / 2; let mut s = 0i64;
            for &t in &wt {
                let (mut l, mut h) = (0, mh as i64);
                while l <= h {
                    let i = (l + h) / 2;
                    if i*(i+1)/2 * t as i64 <= m { l = i + 1 } else { h = i - 1 }
                }
                s += h
            }
            if s < mh as i64 { lo = m + 1 } else { hi = m - 1 }
        } lo
    }