3296. Minimum Number of Seconds to Make Mountain Height Zero

/**
 * Problem: LeetCode 3296 - Minimum Number of Seconds to Make Mountain Height Zero
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int minW = workerTimes[0];
        for (int w : workerTimes) {
            minW = Math.min(minW, w);
        }

        long low = 1L;
        // Upper bound: fastest worker alone reduces the entire mountain
        long high = (long) minW * mountainHeight * (mountainHeight + 1L) / 2L;
        long ans = high;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (canReduce(mid, mountainHeight, workerTimes)) {
                ans = mid;
                high = mid - 1; // Try smaller time
            } else {
                low = mid + 1;
            }
        }

        return ans;
    }

    private boolean canReduce(long time, int mountainHeight, int[] workerTimes) {
        long totalHeight = 0;
        for (int w : workerTimes) {
            long m = time / w;
            if (m > 0) {
                // Solve x * (x + 1) / 2 <= m for x
                long x = (long) ((Math.sqrt(1.0 + 8.0 * m) - 1.0) / 2.0);
                while (x * (x + 1) / 2 > m) {
                    x--;
                }
                while ((x + 1) * (x + 2) / 2 <= m) {
                    x++;
                }
                totalHeight += x;
                if (totalHeight >= mountainHeight) {
                    return true;
                }
            }
        }
        return totalHeight >= mountainHeight;
    }
}

"""
Problem: LeetCode 3296 - Minimum Number of Seconds to Make Mountain Height Zero
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
import math
from typing import List

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        min_w = min(workerTimes)
        low = 1
        # Upper bound: fastest worker alone reduces the entire mountain
        high = min_w * mountainHeight * (mountainHeight + 1) // 2
        ans = high

        def can_reduce(t: int) -> bool:
            total_height = 0
            for w in workerTimes:
                m = t // w
                if m > 0:
                    # Solve x * (x + 1) // 2 <= m
                    x = int((math.isqrt(1 + 8 * m) - 1) // 2)
                    total_height += x
                    if total_height >= mountainHeight:
                        return True
            return total_height >= mountainHeight

        while low <= high:
            mid = (low + high) // 2
            if can_reduce(mid):
                ans = mid
                high = mid - 1
            else:
                low = mid + 1

        return ans

/**
 * Problem: LeetCode 3296 - Minimum Number of Seconds to Make Mountain Height Zero
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

class Solution {
    bool canReduce(long long time, int mountainHeight, const vector<int>& workerTimes) {
        long long totalHeight = 0;
        for (int w : workerTimes) {
            long long m = time / w;
            if (m > 0) {
                // Solve x * (x + 1) / 2 <= m
                long long x = (sqrt(1.0 + 8.0 * m) - 1.0) / 2.0;
                while (x * (x + 1) / 2 > m) {
                    x--;
                }
                while ((x + 1) * (x + 2) / 2 <= m) {
                    x++;
                }
                totalHeight += x;
                if (totalHeight >= mountainHeight) {
                    return true;
                }
            }
        }
        return totalHeight >= mountainHeight;
    }

public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        int minW = *min_element(workerTimes.begin(), workerTimes.end());

        long long low = 1;
        // Upper bound: fastest worker alone reduces the entire mountain
        long long high = (long long)minW * mountainHeight * (mountainHeight + 1LL) / 2LL;
        long long ans = high;

        while (low <= high) {
            long long mid = low + (high - low) / 2;
            if (canReduce(mid, mountainHeight, workerTimes)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return ans;
    }
};

/**
 * Problem: LeetCode 3296 - Minimum Number of Seconds to Make Mountain Height Zero
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number} mountainHeight
 * @param {number[]} workerTimes
 * @return {number}
 */
var minNumberOfSeconds = function(mountainHeight, workerTimes) {
    let minW = workerTimes[0];
    for (let i = 1; i < workerTimes.length; i++) {
        if (workerTimes[i] < minW) {
            minW = workerTimes[i];
        }
    }

    let low = 1n;
    // Upper bound: fastest worker alone reduces the entire mountain
    let high = (BigInt(minW) * BigInt(mountainHeight) * (BigInt(mountainHeight) + 1n)) / 2n;
    let ans = high;

    function sqrt(val) {
        if (val < 0n) return 0n;
        if (val < 2n) return val;
        let x0 = val / 2n;
        let x1 = (x0 + val / x0) / 2n;
        while (x1 < x0) {
            x0 = x1;
            x1 = (x0 + val / x0) / 2n;
        }
        return x0;
    }

    function canReduce(time) {
        let totalHeight = 0n;
        const targetHeight = BigInt(mountainHeight);

        for (let i = 0; i < workerTimes.length; i++) {
            const w = BigInt(workerTimes[i]);
            const m = time / w;
            if (m > 0n) {
                // Solve x * (x + 1) / 2 <= m  =>  x = (sqrt(1 + 8*m) - 1) / 2
                const s = sqrt(1n + 8n * m);
                const x = (s - 1n) / 2n;
                totalHeight += x;
                if (totalHeight >= targetHeight) {
                    return true;
                }
            }
        }
        return totalHeight >= targetHeight;
    }

    while (low <= high) {
        const mid = (low + high) / 2n;
        if (canReduce(mid)) {
            ans = mid;
            high = mid - 1n;
        } else {
            low = mid + 1n;
        }
    }

    return Number(ans);
};