Synced service days
MediumOnline Assessment
Find the k-th day on which every machine in a plant is serviced together.
A plant has several machines, listed in machines as [period, first] pairs. A machine is serviced on day first, then again every period days after that: days first, first + period, first + 2 * period, and so on. It is never serviced on any day before first. Days are whole numbers counted from day 0.
A day is a joint day when every machine is serviced on it. The plant manager wants to schedule one big inspection on the k-th joint day (counting joint days in increasing order, starting from 1).
Input: machines, a list of [period, first] pairs; k, which joint day is wanted.
Output: the day number of the k-th joint day, or -1 if the machines never all meet (that is, there are fewer than k joint days, which can only mean there are none).
Periods are large and the answer can be huge, so stepping through the days one by one will not finish in time. Periods need not be pairwise coprime.
Example 1
- Input:
- [[[4,1],[6,3]],2]
- Output:
- 21
- Explanation
- Machine A is serviced on days 1, 5, 9, 13, 17, 21, ... and machine B on days 3, 9, 15, 21, ... They share days 9, 21, 33, ... (every 12 days). The second shared day is 21.
Example 2
- Input:
- [[[3,10],[5,2]],1]
- Output:
- 22
- Explanation
- Machine A's schedule is 10, 13, 16, 19, 22, ... (it starts on day 10) and machine B's is 2, 7, 12, 17, 22, .... Day 7 would fit both repeating patterns, but machine A is not in service yet on day 7, so the first shared day is 22.
Example 3
- Input:
- [[[4,0],[6,1]],3]
- Output:
- -1
- Explanation
- Machine A is serviced only on multiples of 4, which are even. Machine B is serviced on days 1, 7, 13, ..., which are all odd. They never meet, so the answer is -1.
Constraints
1 <= machines.length <= 8- each machine is
[period, first]with1 <= period <= 1,000,000,000and0 <= first <= 1,000,000,000 1 <= k <= 1,000,000- whenever the requested day exists, it is below 9,000,000,000,000,000