Mínimo común múltiplo de una lista
La misión
Problema
Varios autobuses salen de la misma terminal en el tiempo cero, y el autobús i vuelve cada nums[i] minutos. Devuelve el primer minuto positivo en el que todos están de vuelta en la terminal a la vez, que es el mínimo común múltiplo (MCM) de los valores. Cada valor es un entero positivo y la lista tiene al menos un valor.
Ejemplos
Input: nums = [4, 6, 10]
Output: 60
Por qué: 60 es el menor número divisible entre 4, 6 y 10
Input: nums = [12, 18, 24]
Output: 72
Por qué: los valores comparten factores, así que la respuesta queda muy por debajo de su producto
Input: nums = [9]
Output: 9
Por qué: caso límite: un solo autobús coincide consigo mismo en su primera vuelta
Pistas
0 / 3
Resuélvelo primero para dos valores. Su producto siempre es un múltiplo común, pero cuenta dos veces cada factor compartido.
Para dos valores a y b, el mínimo común múltiplo es igual a a por b dividido entre su máximo común divisor (MCD), y el algoritmo de Euclides encuentra ese divisor rápidamente.
Recorre la lista acumulando: lleva una respuesta parcial que empieza en 1 y combínala con cada valor, uno por uno, usando la fórmula para dos valores. Divide antes de multiplicar para que los números intermedios se mantengan pequeños.
- Tiempo objetivo
- O(n log(max(nums)))
- Espacio objetivo
- O(1)
Restricciones
- every value is a positive integer
- the list holds at least one value
Solución
El mínimo común múltiplo de dos números es su producto dividido entre su máximo común divisor, porque el divisor es exactamente la parte que ambos números aportan y el producto la cuenta dos veces. La operación es asociativa, así que la respuesta para toda la lista se construye incorporando los valores, uno a la vez, a un resultado acumulado. Dividir el resultado acumulado entre el divisor antes de multiplicar mantiene cada valor intermedio no mayor que la respuesta final. Cada paso cuesta una llamada a Euclides, así que el tiempo es O(n log M) para un valor máximo M y el espacio es 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])) # -> 30030¿Lo que te frena es la idea y no el código? MCD y Euclides lo explica.