Least Common Multiple of a List
Problem
Several buses leave the same depot at time zero, and bus i returns every nums[i] minutes. Return the first positive minute at which all of them are back at the depot together, which is the least common multiple of the values. Every value is a positive integer, and the list holds at least one value.
Examples
Input: nums = [4, 6, 10]
Output: 60
Why: 60 is the smallest number divisible by 4, 6 and 10Input: nums = [12, 18, 24]
Output: 72
Why: the values share factors, so the answer is far below their productInput: nums = [9]
Output: 9
Why: edge case, a single bus meets itself on its first returnHints
0 / 3
Solve it for two values first. Their product is always a common multiple, but it counts every shared factor twice.
For two values a and b, the least common multiple equals a times b divided by their greatest common divisor, and Euclid's algorithm finds that divisor quickly.
Fold the list: keep a running answer that starts at 1, and combine it with each value in turn using the two-value formula. Divide before multiplying so the intermediate numbers stay small.
Solution
The least common multiple of two numbers is their product divided by their greatest common divisor, because the divisor is exactly the part both numbers contribute and the product counts it twice. The operation is associative, so the answer for the whole list is built by folding the values into a running result one at a time. Dividing the running result by the divisor before multiplying keeps every intermediate value no larger than the final answer. Each step costs one Euclid call, so time is O(n log M) for largest value M, and space is O(1).
from math import gcd
def lcm_all(nums):
result = 1
for x in nums:
result = result // gcd(result, x) * x # divide first: stays small
return result
print(lcm_all([4, 6, 10])) # -> 60
print(lcm_all([12, 18, 24])) # -> 72
print(lcm_all([9])) # -> 9
print(lcm_all([2, 3, 5, 7, 11, 13])) # -> 30030Stuck on the idea rather than the code? GCD and Euclid covers it.