Minimum Time to Complete Trips - Practice Coding Problems

Minimum Time to Complete Trips - Problem

You are given an array time where time[i] denotes the time taken by the i^th bus to complete one trip.

Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

Input & Output

Example 1 — Basic Case

$ Input: time = [1,2,3], totalTrips = 5

› Output: 3

💡 Note: At time 3: Bus 0 completes 3/1=3 trips, Bus 1 completes 3/2=1 trip, Bus 2 completes 3/3=1 trip. Total: 3+1+1=5 trips.

Example 2 — Slower Buses

$ Input: time = [2], totalTrips = 1

› Output: 2

💡 Note: Only one bus that takes 2 time units per trip. To complete 1 trip, we need exactly 2 time units.

Example 3 — Multiple Fast Buses

$ Input: time = [1,1,1], totalTrips = 10

› Output: 4

💡 Note: At time 4: Each of the 3 buses completes 4 trips, totaling 12 trips which exceeds the required 10.

Constraints

1 ≤ time.length ≤ 10⁵
1 ≤ time[i], totalTrips ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Buses with times [1,2,3] need 5 total trips

Process

Find minimum time where trips ≥ 5

Output

At time 3: buses complete 3+1+1=5 trips

Key Takeaway

🎯 Key Insight: Binary search on time to efficiently find the minimum duration needed for all buses to complete the required trips

Asked in

A Amazon 15 G Google 12 M Microsoft 8 F Facebook 6

The key insight is to use binary search on the answer space rather than checking each time unit sequentially. We search for the minimum time where all buses can complete at least the required number of trips. Best approach is binary search on answer space with Time: O(n log(min(time) × totalTrips)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Linear Time Search	O(min(time) * totalTrips)	O(1)	Check each time unit incrementally until total trips >= target
Binary Search on Answer Space	O(n * log(min(time) * totalTrips))	O(1)	Binary search on possible time values to find minimum time needed

Brute Force - Linear Time Search — Algorithm Steps

Start with time = 1
For each time t, calculate total trips possible
Return first time where trips >= totalTrips

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with time = 1

Check

Count trips possible at current time

Increment

Move to next time until target reached

Code -

solution.c — C

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

long long solution(int* time, int timeSize, int totalTrips) {
    long long currentTime = 1;
    while (1) {
        long long totalCompleted = 0;
        for (int i = 0; i < timeSize; i++) {
            totalCompleted += currentTime / time[i];
        }
        
        if (totalCompleted >= totalTrips) {
            return currentTime;
        }
        
        currentTime++;
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int time[100];
    int timeSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        time[timeSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int totalTrips;
    scanf("%d", &totalTrips);
    
    long long result = solution(time, timeSize, totalTrips);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(min(time) * totalTrips)

In worst case, we check every time unit up to min(time) * totalTrips

✓ 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 Time Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler