Minimum Number of Seconds to Make Mountain Height Zero
MedPrompt
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.
The workers work simultaneously to reduce the height of the mountain. For worker i:
- To decrease the mountain's height by
x, it takesworkerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * xseconds. For example:- To reduce the height of the mountain by 1, it takes
workerTimes[i]seconds. - To reduce the height of the mountain by 2, it takes
workerTimes[i] + workerTimes[i] * 2seconds, and so on.
- To reduce the height of the mountain by 1, it takes
Return an integer representing the minimum number of seconds required for the workers to make the height of the mountain 0.
Example 1:
Input: mountainHeight = 4, workerTimes = [2,1,1]
Output: 3
Explanation:
One way the height of the mountain can be reduced to 0 is:
- Worker 0 reduces the height by 1, taking
workerTimes[0] = 2seconds. - Worker 1 reduces the height by 2, taking
workerTimes[1] + workerTimes[1] * 2 = 3seconds. - Worker 2 reduces the height by 1, taking
workerTimes[2] = 1second.
Since they work simultaneously, the minimum time needed is max(2, 3, 1) = 3 seconds.
Example 2:
Input: mountainHeight = 10, workerTimes = [3,2,2,4]
Output: 12
Explanation:
- Worker 0 reduces the height by 2, taking
workerTimes[0] + workerTimes[0] * 2 = 9seconds. - Worker 1 reduces the height by 3, taking
workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12seconds. - Worker 2 reduces the height by 3, taking
workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12seconds. - Worker 3 reduces the height by 2, taking
workerTimes[3] + workerTimes[3] * 2 = 12seconds.
The number of seconds needed is max(9, 12, 12, 12) = 12 seconds.
Example 3:
Input: mountainHeight = 5, workerTimes = [1]
Output: 15
Explanation:
There is only one worker in this example, so the answer is workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15.
Constraints:
1 <= mountainHeight <= 1051 <= workerTimes.length <= 1041 <= workerTimes[i] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through time, second by second, starting from 1. For each second t, it checks if it's possible for the workers to collectively reduce the mountain's height to zero within that time. The first time t for which this is possible is the minimum time required.
Algorithm
- Initialize
time = 1. - Start an infinite loop.
- Inside the loop, calculate the total height that can be reduced by all workers within the current
time.- Initialize
totalHeightReduced = 0. - For each
workerTimeinworkerTimes:- Find the maximum height
hthis worker can reduce. This can be done by solvingworkerTime * h * (h + 1) / 2 <= timefor the largest integerh. A simple way is to iteratehfrom 1 upwards until the time taken exceeds the currenttime. - Add this
htototalHeightReduced.
- Find the maximum height
- Initialize
- Check if
totalHeightReduced >= mountainHeight. - If it is,
timeis the minimum time required. Returntime. - If not, increment
timeand continue the loop.
Walkthrough
The core idea is to test every possible time value t starting from 1. For a given time t, we need a helper function, let's call it canReduce(t), to determine if the total work done can meet or exceed mountainHeight. Inside canReduce(t), for each worker, we calculate the maximum height they can reduce. The time taken for a worker i to reduce height by h is workerTimes[i] * h * (h + 1) / 2. We need to find the largest integer h such that this time is less than or equal to t. We can find this h by iterating from h=1 upwards until the time exceeds t. Summing up the maximum possible height reduction for all workers gives the total reduction possible within time t. If this total reduction is at least mountainHeight, canReduce(t) returns true. The main function starts a loop t = 1, 2, 3, ... and calls canReduce(t). The first t that returns true is our answer.
class Solution { // This approach is too slow and will time out. public long minSeconds(int mountainHeight, int[] workerTimes) { long time = 1; while (true) { if (canReduce(mountainHeight, workerTimes, time)) { return time; } time++; } } private boolean canReduce(int mountainHeight, int[] workerTimes, long time) { long totalHeightReduced = 0; for (int wt : workerTimes) { long h = 0; while (true) { long nextH = h + 1; // Using long to prevent overflow for timeNeeded long timeNeeded = (long)wt * nextH * (nextH + 1) / 2; if (timeNeeded > time) { break; } h = nextH; } totalHeightReduced += h; if (totalHeightReduced >= mountainHeight) { return true; } } return totalHeightReduced >= mountainHeight; }}Complexity
Time
O(T_opt * N * H), where `T_opt` is the optimal time, `N` is the number of workers, and `H` is the mountain height. This is infeasible as `T_opt` can be very large.
Space
O(1) extra space.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient. The minimum time can be very large (up to ~10^16), leading to a Time Limit Exceeded (TLE) error on most platforms.
This approach improves upon the linear search by recognizing that the problem has a monotonic property: if the mountain can be cleared in t seconds, it can also be cleared in any time greater than t. This allows us to use binary search on the answer (the minimum time). For each time t we test, we determine the maximum height each worker can reduce. This subproblem can also be solved with a binary search.
Algorithm
- Define a search range for time
t.low = 0,high =a large value (e.g.,5 * 10^15).ans = high. - While
low <= high:mid = low + (high - low) / 2.- If
canReduce(mid)is true:midis a potential answer. Store it:ans = mid.- Try for a smaller time:
high = mid - 1.
- Else:
midis too small. Need more time:low = mid + 1.
- Return
ans. canReduce(time)function:totalHeightReduced = 0.- For each
workerTimeinworkerTimes:- Binary search for the max height
hthis worker can reduce in the range[0, mountainHeight]. - Add the found
htototalHeightReduced.
- Binary search for the max height
- Return
totalHeightReduced >= mountainHeight.
Walkthrough
We binary search for the minimum time t in a range [low, high]. low can be 0, and high must be a sufficiently large upper bound (e.g., the time for a single worker with the smallest workerTime to clear the entire mountain). For each mid time value in our binary search, we need to check if it's feasible (canReduce(mid)). To implement canReduce(mid), we calculate the total height all workers can reduce. For each worker i, we need to find the maximum height h_i they can reduce in mid seconds. This means finding the largest integer h_i satisfying workerTimes[i] * h_i * (h_i + 1) / 2 <= mid. Instead of solving this inequality directly with a formula, we can perform another binary search for h_i in the range [0, mountainHeight]. For a guessed height h_guess, we calculate the time required: time_needed = workerTimes[i] * h_guess * (h_guess + 1) / 2. If time_needed <= mid, it means h_guess is achievable, so we try for a larger height. Otherwise, we need to try a smaller height. After finding the max h_i for each worker, we sum them up. If the total sum is at least mountainHeight, then canReduce(mid) is true, and we try for a smaller time t. Otherwise, we need more time.
class Solution { public long minSeconds(int mountainHeight, int[] workerTimes) { long low = 0; long high = 5_000_000_000_000_001L; long ans = high; while (low <= high) { long mid = low + (high - low) / 2; if (canReduce(mountainHeight, workerTimes, mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } private boolean canReduce(int mountainHeight, int[] workerTimes, long time) { long totalHeightReduced = 0; for (int wt : workerTimes) { totalHeightReduced += getMaxHeight(wt, time, mountainHeight); if (totalHeightReduced >= mountainHeight) { return true; // Early exit optimization } } return totalHeightReduced >= mountainHeight; } // Find max height for a worker using binary search private long getMaxHeight(long workerTime, long maxTime, int mountainHeight) { long low = 0; long high = mountainHeight; // A worker can't reduce more than the total height long ans = 0; while (low <= high) { long mid = low + (high - low) / 2; if (mid == 0) { low = mid + 1; continue; } // Use long to prevent overflow long timeNeeded = workerTime * mid * (mid + 1) / 2; if (timeNeeded <= maxTime) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; }}Complexity
Time
O(N * log(H) * log(T_max)), where `N` is the number of workers, `H` is `mountainHeight`, and `T_max` is the upper bound for the search time. This is efficient enough to pass.
Space
O(1) extra space.
Trade-offs
Pros
Significantly more efficient than linear search.
Guaranteed to find the solution within logarithmic time bounds.
Cons
More complex to implement due to the nested binary search structure.
The inner binary search is unnecessary and can be replaced by a direct mathematical calculation, making this approach suboptimal.
This is the most efficient approach. It uses binary search on the answer (the minimum time), similar to the previous approach. However, it optimizes the canReduce(t) check. Instead of using a second binary search to find the maximum height a worker can reduce, it solves the time inequality directly using the quadratic formula. This provides a constant-time O(1) calculation for each worker's contribution, leading to a faster overall solution.
Algorithm
- Define a search range for time
t.low = 0,high =a large value (e.g.,5 * 10^15).ans = high. - While
low <= high:mid = low + (high - low) / 2.- If
canReduce(mid)is true:midis a potential answer. Store it:ans = mid.- Try for a smaller time:
high = mid - 1.
- Else:
midis too small. Need more time:low = mid + 1.
- Return
ans. canReduce(time)function:totalHeightReduced = 0.- For each
workerTimeinworkerTimes:- Calculate
h = floor((-1 + sqrt(1 + 8.0 * time / workerTime)) / 2). - Add
htototalHeightReduced.
- Calculate
- Return
totalHeightReduced >= mountainHeight.
Walkthrough
The overall structure is a binary search on the time t. The key improvement is in the canReduce(t) function. For a given time t and a worker i, we want to find the maximum integer height h such that workerTimes[i] * h * (h + 1) / 2 <= t. This inequality can be rewritten as a quadratic inequality: h^2 + h - (2 * t / workerTimes[i]) <= 0. We can find the positive root of the corresponding equation x^2 + x - C = 0 (where C = 2 * t / workerTimes[i]) using the quadratic formula: x = (-1 + sqrt(1 + 4*C)) / 2. Substituting C back, we get h = (-1 + sqrt(1 + 8 * t / workerTimes[i])) / 2. Since h must be an integer, the maximum height a worker can reduce is floor((-1 + sqrt(1 + 8.0 * t / workerTimes[i])) / 2). This calculation is O(1). In canReduce(t), we iterate through all workers, calculate their maximum reducible height using this formula, and sum them up. If the total height is at least mountainHeight, t is feasible. The binary search then proceeds as usual to find the minimum such t.
class Solution { public long minSeconds(int mountainHeight, int[] workerTimes) { long low = 0; long high = 5_000_000_000_000_001L; long ans = high; while (low <= high) { long mid = low + (high - low) / 2; if (canReduce(mountainHeight, workerTimes, mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } private boolean canReduce(int mountainHeight, int[] workerTimes, long time) { long totalHeightReduced = 0; for (int wt : workerTimes) { // Solve h^2 + h - (2 * time / wt) <= 0 // Positive root of x^2 + x - C = 0 is (-1 + sqrt(1 + 4C)) / 2 // C = 2.0 * time / wt double c = 2.0 * time / wt; // Use double for precision in sqrt long h = (long) ((-1 + Math.sqrt(1 + 4 * c)) / 2.0); totalHeightReduced += h; if (totalHeightReduced >= mountainHeight) { return true; // Early exit optimization } } return totalHeightReduced >= mountainHeight; }}Complexity
Time
O(N * log(T_max)), where `N` is the number of workers and `T_max` is the upper bound for the search time. This is very fast and will pass all test cases.
Space
O(1) extra space.
Trade-offs
Pros
Most efficient solution.
The
canReducecheck is very fast, taking linear time with respect to the number of workers.
Cons
Requires understanding how to transform the problem into a solvable inequality.
Potential for floating-point precision issues if not handled carefully (using
doublefor intermediate calculations is important).
Solutions
Solution
class Solution {private int mountainHeight;private int[] workerTimes;public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) { this.mountainHeight = mountainHeight; this.workerTimes = workerTimes; long l = 1, r = (long)1 e16; while (l < r) { long mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; }private boolean check(long t) { long h = 0; for (int wt : workerTimes) { h += (long)(Math.sqrt(t * 2.0 / wt + 0.25) - 0.5); } return h >= mountainHeight; }}class Solution {public: long long minNumberOfSeconds(int mountainHeight, vector<int> &workerTimes) { using ll = long long; ll l = 1, r = 1e16; auto check = [&](ll t) -> bool { ll h = 0; for (int &wt : workerTimes) { h += (long long)(sqrt(t * 2.0 / wt + 0.25) - 0.5); } return h >= mountainHeight; }; while (l < r) { ll mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l; }};class Solution: def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int: def check(t: int) -> bool: h = 0 for wt in workerTimes: h += int(sqrt(2 * t / wt + 1 / 4) - 1 / 2) return h >= mountainHeight return bisect_left(range(10 ** 16), True, key=check)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.