Bus Timetable Sync
Easy · math
Several bus routes all leave the depot together at minute 0. After that, route i leaves again every gaps[i] minutes: at minute gaps[i], then 2 * gaps[i], then 3 * gaps[i], and so on.
Return the first minute after 0 at which every route leaves at the very same moment.
The list always has at least one route, so there is always an answer. It is guaranteed that the answer is at most 10^12, which is too big for a 32-bit integer, so use a 64-bit type in languages where that matters. With a single route, the answer is simply that route's gap.
Examples
Example 1
Input: gaps = [4, 6]
Output: 12
Route 0 leaves at 4, 8, 12 and route 1 leaves at 6, 12. Minute 12 is the first shared one.
Example 2
Input: gaps = [3, 5, 15]
Output: 15
Minute 15 is a multiple of 3, 5 and 15, and no smaller positive minute is.
Example 3
Input: gaps = [7]
Output: 7
Constraints
- 1 <= len(gaps) <= 10^4
- 1 <= gaps[i] <= 10^12
- The answer is at most 10^12.