A city intersection has several traffic lights. Each light i turns green every c_i seconds (it is green at time 0, c_i, 2*c_i, ...). All lights start green at time 0.
Given the cycle lengths of n lights, find the first strictly-positive time at which every light is green simultaneously again.
Line 1: an integer n.
Line 2: n space-separated integers, the cycle lengths c_1 .. c_n.
A single integer: the smallest positive time at which all lights are green together.
Example 1
Input
3 2 3 4
Expected
12
Explanation
LCM(2, 3, 4) = 12: the lights next align together at t=12.
Example 2
Input
1 7
Expected
7
Explanation
With only one light, it realigns with itself every 7 seconds.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →