Minimum Number of Seconds to Make Mountain Height Zero — Medium Problem & Solution

Problem statement

A mountain is mountainHeight units tall. A team of workers digs it down at the same time; worker i has speed parameter workerTimes[i].

For worker i to remove x units, it needs workerTimes[i] · (1 + 2 + ... + x) = workerTimes[i] · x · (x + 1) / 2 seconds — each further unit takes longer than the last. Workers act independently and in parallel, and you choose how many units each one removes (some may remove none).

Return the minimum number of seconds until the mountain's height is 0.

CodeKairo bounds: the original allows heights up to 10^5 and times up to 10^6, which needs a 64-bit answer. Here mountainHeight <= 1000 and workerTimes[i] <= 1000, so the answer fits in a 32-bit integer.

Example 1

Input: mountainHeight = 6, workerTimes = [1,3]
Output: 10
Explanation: The fast worker removes 4 units (1 + 2 + 3 + 4 = 10 s) while the slow one removes 2 (3 + 6 = 9 s).

Example 2

Input: mountainHeight = 5, workerTimes = [1]
Output: 15

Example 3

Input: mountainHeight = 3, workerTimes = [5,5,5]
Output: 5
Explanation: Each worker removes one unit.

Constraints

• 1 <= mountainHeight <= 1000
• 1 <= workerTimes.length <= 10^4
• 1 <= workerTimes[i] <= 1000

How to solve Minimum Number of Seconds to Make Mountain Height Zero

Binary search on the finishing time. For a candidate time T, every worker removes as much as it can by T, and the mountain is cleared exactly when those amounts sum to the height.

Approach

1. Search T between 1 and min(workerTimes) · h · (h + 1) / 2 (the fastest worker alone always finishes by then).
2. For a candidate T, for each worker find the largest x in [0, h] with t · x · (x + 1) / 2 <= T (inner binary search, or x = floor((sqrt(8 · floor(T / t) + 1) - 1) / 2)).
3. Sum the x values; stop early once the sum reaches h. T is feasible if it does.
4. Keep the smallest feasible T.

Why it works

Workers do not interact, so by time T the most the team can remove is the sum of each worker's individual maximum, and any split that removes h units by T is dominated by it. That maximum grows with T, so feasibility is monotone and the binary search is exact.

Complexity

• Time — O(w · log h · log(T_max))
• Space — O(1)

Pitfalls

• Work with t · x · (x + 1) / 2 in 64-bit — with the original bounds it reaches about 5 · 10^15.
• Cap each worker's x at the height so the sum cannot overflow.
• A floating-point square root can be off by one; correct it or use integer arithmetic.

Reference solution

Python

from typing import List
import math

def minNumberOfSeconds(mountainHeight: int, workerTimes: List[int]) -> int:
    h = mountainHeight

    def enough(T):
        done = 0
        for t in workerTimes:
            m = T // t
            x = (math.isqrt(8 * m + 1) - 1) // 2
            done += min(x, h)
            if done >= h:
                return True
        return False

    lo, hi = 1, min(workerTimes) * h * (h + 1) // 2
    while lo < hi:
        mid = (lo + hi) // 2
        if enough(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var minNumberOfSeconds = function(mountainHeight, workerTimes) {
    var h = mountainHeight;
    var enough = function(T) {
        var done = 0;
        for (var i = 0; i < workerTimes.length; i++) {
            var t = workerTimes[i];
            var lo = 0, hi = h;
            while (lo < hi) {
                var mid = (lo + hi + 1) >> 1;
                if (t * mid * (mid + 1) / 2 <= T) lo = mid; else hi = mid - 1;
            }
            done += lo;
            if (done >= h) return true;
        }
        return false;
    };
    var fastest = workerTimes[0];
    for (var j = 1; j < workerTimes.length; j++) if (workerTimes[j] < fastest) fastest = workerTimes[j];
    var lo = 1, hi = fastest * h * (h + 1) / 2;
    while (lo < hi) {
        var mid = lo + Math.floor((hi - lo) / 2);
        if (enough(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium