Course4all

Minimum Time to Complete Trips

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

Minimum Time to Complete Trips

You are given an array time where time[i] denotes the time taken by the ii-th bus to complete one trip. Return the minimum time required for all buses to complete at least totalTrips trips.
Medium

Examples

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

Level I: Brute Force

Intuition

Iterate from time T=1T=1 upwards and check if the total trips sumlfloorT/time[i]rfloor\\sum \\lfloor T / time[i] \\rfloor reaches totalTrips.
⏱ $O(MinTime \\cdot TotalTrips)$💾 $O(1)$

Detailed Dry Run

time = [1,2,3], totalTrips = 5
  • T=1: trips = 1/1 + 1/2 + 1/3 = 1 < 5
  • T=2: trips = 2/1 + 2/2 + 2/3 = 3 < 5
  • T=3: trips = 3/1 + 3/2 + 3/3 = 5 >= 5. Return 3.
java
class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long t = 1;
        while (true) {
            long trips = 0;
            for (int b : time) trips += t / b;
            if (trips >= totalTrips) return t;
            t++;
        }
    }
}
Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

The number of trips is monotone relative to time. We can binary search the answer range [1, min(time) * totalTrips].
⏱ $O(N \\cdot \\log(MinTime \\cdot TotalTrips))$💾 $O(1)$

Detailed Dry Run

StepLRMidTripsDecision
11535R = 3
21323L = 3
Exit----Return 3
java
class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long l = 1, r = (long)time[0] * totalTrips;
        for (int t : time) r = Math.min(r, (long)t * totalTrips);
        while (l < r) {
            long m = l + (r - l) / 2, trips = 0;
            for (int t : time) trips += m / t;
            if (trips >= totalTrips) r = m; else l = m + 1;
        }
        return l;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionFind K-th Smallest Pair Distance
Next Question →Maximum Running Time of N Computers