Minimum Number of Seconds to Make Mountain Height Zero

Minimum Number of Seconds to Make Mountain Height Zero - Problem

Array Math Binary Search Greedy Heap (Priority Queue) Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: mountainHeight = 4, workerTimes = [2,1,1]

› Output: 3

💡 Note: Worker 1 reduces 1 unit (time: 2), Worker 2 reduces 2 units (time: 1+2=3), Worker 3 reduces 1 unit (time: 1). Maximum time is 3.

Example 2 — Single Worker

$ Input: mountainHeight = 3, workerTimes = [3]

› Output: 18

💡 Note: Only worker reduces all 3 units: 3×1 + 3×2 + 3×3 = 3 + 6 + 9 = 18 seconds.

Example 3 — Equal Workers

$ Input: mountainHeight = 5, workerTimes = [1,1]

› Output: 6

💡 Note: Optimal distribution: Worker 1 gets 3 units (1+2+3=6), Worker 2 gets 2 units (1+2=3). Maximum time is 6.

Constraints

1 ≤ mountainHeight ≤ 10⁵
1 ≤ workerTimes.length ≤ 10⁴
1 ≤ workerTimes[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Mountain height=4, workers=[2,1,1] with increasing work per unit

Process

Distribute work optimally among workers working simultaneously

Output

Minimum time=3 when work is distributed efficiently

Key Takeaway

🎯 Key Insight: Binary search on the total time needed, then verify if workers can collectively finish within that time using optimal work distribution

Asked in

G Google 15 M Microsoft 12 a Amazon 10 f Meta 8

The key insight is to use binary search on the answer - the total time needed. For each candidate time, we check if workers can collectively reduce the mountain to zero using the quadratic formula to determine maximum units each worker can complete. Best approach is Binary Search on Answer with Time: O(log(maxTime) × n × √h), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Assignments	O(mountainHeight^workerCount)	O(mountainHeight)	Generate all possible ways to assign height reductions to workers
Binary Search on Answer	O(log(maxTime) × n × √h)	O(1)	Binary search on the total time, check if workers can finish within that time
Greedy with Priority Queue	O(h × log n)	O(n)	Always assign the next unit to the worker who can complete it fastest

Brute Force - Try All Assignments — Algorithm Steps

Generate all partitions of mountainHeight into len(workerTimes) parts
For each partition, calculate time for each worker using arithmetic series
Return minimum time across all partitions

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Create all ways to split height among workers

Calculate Times

For each assignment, compute worker times using arithmetic series

Find Minimum

Return the minimum maximum time across all assignments

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long calculateTime(int workerIdx, int units, int* workerTimes) {
    if (units == 0) return 0;
    return (long long) workerTimes[workerIdx] * units * (units + 1) / 2;
}

long long backtrack(int remainingHeight, int workerIdx, int* workerTimes, int workerCount) {
    if (workerIdx == workerCount) {
        return remainingHeight > 0 ? LLONG_MAX : 0;
    }
    
    long long minTime = LLONG_MAX;
    for (int units = 0; units <= remainingHeight; units++) {
        long long workerTime = calculateTime(workerIdx, units, workerTimes);
        long long remainingTime = backtrack(remainingHeight - units, workerIdx + 1, workerTimes, workerCount);
        long long totalTime = workerTime > remainingTime ? workerTime : remainingTime;
        if (totalTime < minTime) {
            minTime = totalTime;
        }
    }
    
    return minTime;
}

long long solution(int mountainHeight, int* workerTimes, int workerCount) {
    return backtrack(mountainHeight, 0, workerTimes, workerCount);
}

int main() {
    int mountainHeight;
    scanf("%d", &mountainHeight);
    
    char line[1000];
    scanf(" %[^\n]", line);
    
    int workerTimes[100];
    int workerCount = 0;
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        workerTimes[workerCount++] = atoi(ptr);
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        if (*ptr == ',') ptr++;
    }
    
    printf("%lld\n", solution(mountainHeight, workerTimes, workerCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mountainHeight^workerCount)

Generate all ways to partition mountainHeight among workers, exponential combinations

✓ Linear Growth

Space Complexity

O(mountainHeight)

Recursion stack depth for generating partitions

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Assignments — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler