Minimum Speed to Arrive on Time - Practice Coding Problems

Minimum Speed to Arrive on Time - Problem

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the i^th train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

For example: If the 1st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2nd train ride at the 2 hour mark.

Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 10⁷ and hour will have at most two digits after the decimal point.

Input & Output

Example 1 — Basic Case

$ Input: dist = [1,1,2], hour = 4.0

› Output: 1

💡 Note: At speed 1: Train 1 takes ceil(1/1)=1 hour, Train 2 takes ceil(1/1)=1 hour, Train 3 takes 2/1=2 hours. Total: 1+1+2=4.0 hours ≤ 4.0

Example 2 — Need Higher Speed

$ Input: dist = [1,1,100000], hour = 2.01

› Output: 10000000

💡 Note: Need very high speed for last train. At speed 10^7: ceil(1/10^7) + ceil(1/10^7) + 100000/10^7 = 1+1+0.01 = 2.01 hours

Example 3 — Impossible Case

$ Input: dist = [1,1,1], hour = 2.0

› Output: -1

💡 Note: Need at least 2 integer hours for first 2 trains, plus time for last train. Minimum time is 2+ε > 2.0, so impossible

Constraints

n == dist.length
1 ≤ n ≤ 10⁵
1 ≤ dist[i] ≤ 10⁵
1 ≤ hour ≤ 10⁹
There will be at most two digits after the decimal point in hour.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of distances and time limit

Process

Calculate time for each speed, considering integer hour waits

Output

Minimum speed that allows on-time arrival

Key Takeaway

🎯 Key Insight: Binary search on answer works because the problem has monotonic property - if speed X works, any speed > X also works

Asked in

G Google 12 a Amazon 8 M Microsoft 6 f Facebook 5

The key insight is to use binary search on the answer space. Since if speed X works, any speed > X also works (monotonic property), we can binary search to find the minimum working speed. The optimal approach is binary search on answer with Time: O(n × log(10⁷)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Linear Search	O(answer × n)	O(1)	Try every speed from 1 upwards until we find one that works
Binary Search on Answer	O(n × log(10^7))	O(1)	Binary search on the speed value to find the minimum speed that works

Brute Force Linear Search — Algorithm Steps

Step 1: Try speed = 1, 2, 3, ... up to 10^7
Step 2: For each speed, calculate total travel time
Step 3: Return first speed that works within the time limit

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Testing

Begin with speed = 1

Calculate Time

For each speed, compute total travel time

Check Constraint

Return first speed where total_time ≤ hour

Code -

solution.c — C

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

int canReachOnTime(int* dist, int n, double hour, int speed) {
    double totalTime = 0;
    
    for (int i = 0; i < n - 1; i++) {
        // All trains except last must wait for next integer hour
        totalTime += ceil((double) dist[i] / speed);
    }
    // Last train doesn't need to wait
    totalTime += (double) dist[n - 1] / speed;
    
    return totalTime <= hour;
}

int solution(int* dist, int n, double hour) {
    // If we have more trains than hours (minus 1), impossible
    if (n - 1 >= hour) {
        return -1;
    }
    
    // Try speeds from 1 to 10^7
    for (int speed = 1; speed <= 10000000; speed++) {
        if (canReachOnTime(dist, n, hour, speed)) {
            return speed;
        }
    }
    
    return -1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int dist[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            dist[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    double hour;
    scanf("%lf", &hour);
    
    printf("%d\n", solution(dist, n, hour));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(answer × n)

Try up to 10^7 speeds, each taking O(n) time to validate

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 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 Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler