Saltar al contenido

Mínimo común múltiplo de una lista

Fácil#gcd#lcm~15 min

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

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

¿Lo que te frena es la idea y no el código? MCD y Euclides lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio