3296. Minimum Number of Seconds to Make Mountain Height Zero

Description

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.

Each worker may reduce the mountain's height by any non-negative integer amount. If worker i reduces the height by x, then:

reducing the first unit of height takes workerTimes[i] seconds,
reducing the second unit takes workerTimes[i] * 2 seconds,
...
reducing the x-th unit takes workerTimes[i] * x seconds.

The total time spent by worker i is the sum of the times required for all x units they reduce. As all workers operate simultaneously, the total time required is the maximum time spent by any worker.

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 <= 10⁵
1 <= workerTimes.length <= 10⁴
1 <= workerTimes[i] <= 10⁶

Solutions

Solution 1: Binary Search

We notice that if all workers can reduce the mountain height to \(0\) in \(t\) seconds, then for any \(t' > t\), the workers can also reduce the mountain height to \(0\) in \(t'\) seconds. Therefore, we can use binary search to find the minimum \(t\) such that the workers can reduce the mountain height to \(0\) in \(t\) seconds.

We define a function \(\textit{check}(t)\), which indicates whether the workers can reduce the mountain height to \(0\) in \(t\) seconds. Specifically, we iterate through each worker. For the current worker \(\textit{workerTimes}[i]\), assuming they reduce the height by \(h'\) in \(t\) seconds, we can derive the inequality:

\[ \left(1 + h'\right) \cdot \frac{h'}{2} \cdot \textit{workerTimes}[i] \leq t \]

Solving the inequality, we get:

\[ h' \leq \left\lfloor \sqrt{\frac{2t}{\textit{workerTimes}[i]} + \frac{1}{4}} - \frac{1}{2} \right\rfloor \]

We can sum up all the \(h'\) values for the workers to get the total reduced height \(h\). If \(h \geq \textit{mountainHeight}\), it means the workers can reduce the mountain height to \(0\) in \(t\) seconds.

Next, we determine the left boundary of the binary search \(l = 1\). Since there is at least one worker, and each worker's working time does not exceed \(10^6\), to reduce the mountain height to \(0\), it takes at least \((1 + \textit{mountainHeight}) \cdot \textit{mountainHeight} / 2 \cdot \textit{workerTimes}[i] \leq 10^{16}\) seconds. Therefore, we can set the right boundary of the binary search to \(r = 10^{16}\). Then, we continuously halve the interval \([l, r]\) until \(l = r\). At this point, \(l\) is the answer.

The time complexity is \(O(n \times \log M)\), where \(n\) is the number of workers, and \(M\) is the right boundary of the binary search, which is \(10^{16}\) in this problem. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRustJavaScriptC#

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)

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) 1e16;
        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;
    }
};

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
    return int64(sort.Search(1e16, func(t int) bool {
        var h int64
        for _, wt := range workerTimes {
            h += int64(math.Sqrt(float64(t)*2.0/float64(wt)+0.25) - 0.5)
        }
        return h >= int64(mountainHeight)
    }))
}

function minNumberOfSeconds(mountainHeight: number, workerTimes: number[]): number {
    const check = (t: bigint): boolean => {
        let h = BigInt(0);
        for (const wt of workerTimes) {
            h += BigInt(Math.floor(Math.sqrt((Number(t) * 2.0) / wt + 0.25) - 0.5));
        }
        return h >= BigInt(mountainHeight);
    };

    let l = BigInt(1);
    let r = BigInt(1e16);

    while (l < r) {
        const mid = (l + r) >> BigInt(1);
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1n;
        }
    }

    return Number(l);
}

impl Solution {
    pub fn min_number_of_seconds(mountain_height: i32, worker_times: Vec<i32>) -> i64 {
        let mut l: i64 = 1;
        let mut r: i64 = 10_i64.pow(16);

        let check = |t: i64| -> bool {
            let mut h: i64 = 0;
            for &wt in &worker_times {
                let wt = wt as f64;
                let t_f = t as f64;
                let val = ((t_f * 2.0 / wt + 0.25).sqrt() - 0.5).floor() as i64;
                h += val;
                if h >= mountain_height as i64 {
                    return true;
                }
            }
            h >= mountain_height as i64
        };

        while l < r {
            let mid = (l + r) >> 1;
            if check(mid) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        l
    }
}

/**
 * @param {number} mountainHeight
 * @param {number[]} workerTimes
 * @return {number}
 */
var minNumberOfSeconds = function (mountainHeight, workerTimes) {
    const check = t => {
        let h = 0n;
        for (const wt of workerTimes) {
            h += BigInt(Math.floor(Math.sqrt((Number(t) * 2.0) / wt + 0.25) - 0.5));
        }
        return h >= BigInt(mountainHeight);
    };

    let l = 1n;
    let r = 10000000000000000n;

    while (l < r) {
        const mid = (l + r) >> 1n;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1n;
        }
    }

    return Number(l);
};

public class Solution {
    public long MinNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        long l = 1, r = (long)1e16;

        bool Check(long t) {
            long h = 0;
            foreach (int wt in workerTimes) {
                long val = (long)(Math.Sqrt(t * 2.0 / wt + 0.25) - 0.5);
                h += val;
                if (h >= mountainHeight) {
                    return true;
                }
            }
            return h >= mountainHeight;
        }

        while (l < r) {
            long mid = (l + r) >> 1;
            if (Check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }
}

3296. Minimum Number of Seconds to Make Mountain Height Zero

Description

Solutions

Solution 1: Binary Search

Comments