1424. Joint Departure Count
Two bus lines start from the same stop at time 0. Line one leaves again every a minutes and line two every b minutes. Count how many moments t in the range [1, horizon] have both buses leaving the stop at the same minute, and return that count. Time 0 is not counted. The least common multiple of a and b can be as large as 1018, so compute it as a / gcd(a, b) * b and, before multiplying, return 0 when a / gcd(a, b) already exceeds horizon / b. The expected running time is O(log(min(a, b))) with O(1) extra space.
Example 1
- Input:
- a = 4, b = 6, horizon = 100
- Output:
- 8
- Explanation:
The buses meet every lcm(4,6) = 12 minutes, so at 12, 24, ..., 96, which is 8 moments.
Example 2
- Input:
- a = 2, b = 3, horizon = 5
- Output:
- 0
- Explanation:
The first common departure is at minute 6, which is beyond the horizon, so the answer is 0.
Constraints
1 ≤ a, b ≤ 109
1 ≤ horizon ≤ 1015
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log min(a, b))
- Space
- O(1)