<p>You are given an array <code>time</code> where <code>time[i]</code> denotes the time taken by the <code>i<sup>th</sup></code> bus to complete <strong>one trip</strong>.</p>

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

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> time = [1,2,3], totalTrips = 5
<strong>Output:</strong> 3
<strong>Explanation:</strong>
- At time t = 1, the number of trips completed by each bus are [1,0,0]. 
  The total number of trips completed is 1 + 0 + 0 = 1.
- At time t = 2, the number of trips completed by each bus are [2,1,0]. 
  The total number of trips completed is 2 + 1 + 0 = 3.
- At time t = 3, the number of trips completed by each bus are [3,1,1]. 
  The total number of trips completed is 3 + 1 + 1 = 5.
So the minimum time needed for all buses to complete at least 5 trips is 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> time = [2], totalTrips = 1
<strong>Output:</strong> 2
<strong>Explanation:</strong>
There is only one bus, and it will complete its first trip at t = 2.
So the minimum time needed to complete 1 trip is 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= time.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= time[i], totalTrips &lt;= 10<sup>7</sup></code></li>
</ul>

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        # we can guess for each possible value time value: for each bus, it can, in x minutes, complete time[i]
        # * x trips.  the answer is the minimum x value for which the sum of each bus[i] * x >= totalTrips.
        
        # Clearly, for any failing value of x, all values < x also fail, since we need MORE time, not less.
        # (an x value fails if, for each bus[i] * x, the sum of (bus[i] + bus[i + 1] + ...) * x < totalTrips).
        # Furthermore, if an x value succeeds (where (bus[i] + bus[i + 1] + ...) * x >= totalTrips), then all
        # time values > x also work.  Meaning, there is no need to recheck that range. binary search works!

        # defining our minimum time value is easy: just use 1. what should our max be? TotalTrips * max(time)
        # could work, since our time obviously won't exceed that amount (imagine the longest-time bus making
        # each trip, totalTrips times).  Perhaps a more narrower max is totalTrips * min(time), since 
        # that clearly also works (just run the shortest bus totalTrips times) and is always going to be <=
        # totalTrips * max(time).
        
        l, r = 1, max(time) * totalTrips
        ans = r
        while l <= r:
            guessTime = l + (r - l) // 2
            cumulativeTrips = 0 # a running value for how many trips we can make in guessTime
            flag = False
            #print('l, r =', l, r)
            #print('guessTime = ', guessTime)
            for tripTime in time:
                
                numTrips = guessTime // tripTime
             #   print('numTrips = ', numTrips)
                cumulativeTrips += numTrips
                if cumulativeTrips >= totalTrips:
                    ans = guessTime
                    r = guessTime - 1
                    flag = True
                    break

            if not flag: # need more time
                l = guessTime + 1
            #print()

        return ans
                
1389