# Minimum Number of Seconds to Make Mountain Height Zero
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-seconds-to-make-mountain-height-zero)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-seconds-to-make-mountain-height-zero
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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 takes `workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x` seconds. 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] * 2` seconds, and so on.

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] = 2` seconds.
* Worker 1 reduces the height by 2, taking `workerTimes[1] + workerTimes[1] * 2 = 3` seconds.
* Worker 2 reduces the height by 1, taking `workerTimes[2] = 1` second.

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 = 9` seconds.
* Worker 1 reduces the height by 3, taking `workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12` seconds.
* Worker 2 reduces the height by 3, taking `workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12` seconds.
* Worker 3 reduces the height by 2, taking `workerTimes[3] + workerTimes[3] * 2 = 12` seconds.

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 <= 105`
* `1 <= workerTimes.length <= 104`
* `1 <= workerTimes[i] <= 106`

# Approaches
## Brute Force: Linear Search for Minimum Time
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Initialize `time = 1`.
2. Start an infinite loop.
3. Inside the loop, calculate the total height that can be reduced by all workers within the current `time`.
    - Initialize `totalHeightReduced = 0`.
    - For each `workerTime` in `workerTimes`:
        - Find the maximum height `h` this worker can reduce. This can be done by solving `workerTime * h * (h + 1) / 2 <= time` for the largest integer `h`. A simple way is to iterate `h` from 1 upwards until the time taken exceeds the current `time`.
        - Add this `h` to `totalHeightReduced`.
4. Check if `totalHeightReduced >= mountainHeight`.
5. If it is, `time` is the minimum time required. Return `time`.
6. If not, increment `time` and continue the loop.

## Binary Search on Time with Nested Search for Height
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Define a search range for time `t`. `low = 0`, `high =` a large value (e.g., `5 * 10^15`). `ans = high`.
2. While `low <= high`:
    - `mid = low + (high - low) / 2`.
    - If `canReduce(mid)` is true:
        - `mid` is a potential answer. Store it: `ans = mid`.
        - Try for a smaller time: `high = mid - 1`.
    - Else:
        - `mid` is too small. Need more time: `low = mid + 1`.
3. Return `ans`.
4. **`canReduce(time)` function:**
    - `totalHeightReduced = 0`.
    - For each `workerTime` in `workerTimes`:
        - Binary search for the max height `h` this worker can reduce in the range `[0, mountainHeight]`.
        - Add the found `h` to `totalHeightReduced`.
    - Return `totalHeightReduced >= mountainHeight`.

## Optimal: Binary Search on Time with Direct Calculation
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.
**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.
**Pros:** Most efficient solution.; The `canReduce` check 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 `double` for intermediate calculations is important).
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
1. Define a search range for time `t`. `low = 0`, `high =` a large value (e.g., `5 * 10^15`). `ans = high`.
2. While `low <= high`:
    - `mid = low + (high - low) / 2`.
    - If `canReduce(mid)` is true:
        - `mid` is a potential answer. Store it: `ans = mid`.
        - Try for a smaller time: `high = mid - 1`.
    - Else:
        - `mid` is too small. Need more time: `low = mid + 1`.
3. Return `ans`.
4. **`canReduce(time)` function:**
    - `totalHeightReduced = 0`.
    - For each `workerTime` in `workerTimes`:
        - Calculate `h = floor((-1 + sqrt(1 + 8.0 * time / workerTime)) / 2)`.
        - Add `h` to `totalHeightReduced`.
    - Return `totalHeightReduced >= mountainHeight`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```