3296. Minimum Number of Seconds to Make Mountain Height Zero LeetCode Solution

In this guide, you will get 3296. Minimum Number of Seconds to Make Mountain Height Zero LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Seconds to Make Mountain Height Zero problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Number of Seconds to Make Mountain Height Zero solution in C++
4. Minimum Number of Seconds to Make Mountain Height Zero solution in Java
5. Minimum Number of Seconds to Make Mountain Height Zero solution in Python
6. Additional Resources

Problem Statement of Minimum Number of Seconds to Make Mountain Height Zero

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

Complexity Analysis

• Time Complexity: O(n\log(\min(\texttt{workerTimes}) \cdot \texttt{mountainHeight}^2))
• Space Complexity: O(1)

3296. Minimum Number of Seconds to Make Mountain Height Zero LeetCode Solution in C++

class Solution {
 public:
  long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
    long l = 1;
    long r = static_cast<long>(ranges::min(workerTimes)) * mountainHeight *
             (mountainHeight + 1) / 2;

    while (l < r) {
      const long m = (l + r) / 2;
      if (getReducedHeight(workerTimes, m) < mountainHeight)
        l = m + 1;
      else
        r = m;
    }

    return l;
  }

 private:
  // Returns the total height reduced by all workers in `m` seconds.
  int getReducedHeight(const vector<int>& workerTimes, long m) {
    int reducedHeight = 0;
    for (const int workerTime : workerTimes)
      // The height `x` that a worker with working time `w` reduces in `m`
      // seconds.
      // w * (1 + 2 + ... + x) <= m
      //       (1 + x) * x / 2 <= m / w
      //   x^2 + x - 2 * m / w <= 0
      //                     x <= (-1 + sqrt(1 + 8 * m / w)) / 2
      reducedHeight += (-1 + sqrt(1 + 8 * m / workerTime)) / 2;
    return reducedHeight;
  }
};
/* code provided by PROGIEZ */

3296. Minimum Number of Seconds to Make Mountain Height Zero LeetCode Solution in Java

class Solution {
  public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
    long l = 1;
    long r = (long) Arrays.stream(workerTimes).min().getAsInt() * mountainHeight *
             (mountainHeight + 1) / 2;

    while (l < r) {
      final long m = (l + r) / 2;
      if (getReducedHeight(workerTimes, m) < mountainHeight)
        l = m + 1;
      else
        r = m;
    }

    return l;
  }

  // Returns the total height reduced by all workers in `m` seconds.
  private int getReducedHeight(int[] workerTimes, long m) {
    int reducedHeight = 0;
    for (int workerTime : workerTimes)
      // The height `x` that a worker with working time `w` reduces in `m`
      // seconds.
      // w * (1 + 2 + ... + x) <= m
      //       (1 + x) * x / 2 <= m / w
      //   x^2 + x - 2 * m / w <= 0
      //                     x <= (-1 + sqrt(1 + 8 * m / w)) / 2
      reducedHeight += (int) ((-1 + Math.sqrt(1 + 8 * m / workerTime)) / 2);
    return reducedHeight;
  }
}
// code provided by PROGIEZ

3296. Minimum Number of Seconds to Make Mountain Height Zero LeetCode Solution in Python

class Solution:
  def minNumberOfSeconds(
      self,
      mountainHeight: int,
      workerTimes: list[int]
  ) -> int:
    def getReducedHeight(m: int) -> int:
      """Returns the total height reduced by all workers in `m` seconds."""
      # The height `x` that a worker with working time `w` reduces in `m`
      # seconds.
      # w * (1 + 2 + ... + x) <= m
      #       (1 + x) * x / 2 <= m / w
      #   x^2 + x - 2 * m / w <= 0
      #                     x <= (-1 + sqrt(1 + 8 * m / w)) / 2
      return sum((-1 + math.sqrt(1 + 8 * m // workerTime)) // 2
                 for workerTime in workerTimes)

    l = 1
    r = min(workerTimes) * mountainHeight * (mountainHeight + 1) // 2
    return bisect.bisect_left(range(l, r), mountainHeight,
                              key=getReducedHeight) + l
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.