Shuttle Fleet Trip Quota

Medium

A company runs several shuttles. Shuttle i completes one trip in exactly lap[i] minutes and starts the next trip right away. The shuttles run at the same time without affecting each other, and all of them start at minute 0. Together they must complete at least quota trips. Return the smallest whole number of minutes by which that happens. Only finished trips count.

Example 1

lap=[2, 3, 6], quota=6 → 6

By minute 6 the shuttles have made 3, 2 and 1 trips: exactly 6. At minute 5 there would only be 2 + 1 + 0 = 3.

Example 2

lap=[4, 4], quota=3 → 8

By minute 8 each shuttle has made 2 trips, 4 ≥ 3 in total; at minute 7 each has made only one.

Example 3

lap=[5], quota=1 → 5

Constraints

1 ≤ len(lap) ≤ 10⁵
1 ≤ lap[i] ≤ 10⁷
1 ≤ quota ≤ 10⁷

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

Find in a Shifted Sorted Array Medium First and Last Copy Medium Find in a Row-Chained Grid Medium Find in a Shifted Array With Repeats Medium Minimum of a Shifted List Medium

Input

lap=[2, 3, 6], quota=6

Expected

Run checks the first 3 tests in your browser. Submit checks all 106 tests on the server, hidden ones included.