Skip to content

3296. Minimum Number of Seconds to Make Mountain Height Zero 👍

  • Time: $O(n\log(\min(\texttt{workerTimes}) \cdot \texttt{mountainHeight}^2))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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