Pular para o conteúdo

Mínimo múltiplo comum de uma lista

Fácil#gcd#lcm~15 min

A missão

Problema

Vários ônibus saem da mesma garagem no instante zero, e o ônibus i volta a cada nums[i] minutos. Retorne o primeiro minuto positivo em que todos estão de volta à garagem ao mesmo tempo, ou seja, o MMC (LCM) dos valores. Todo valor é um inteiro positivo, e a lista tem pelo menos um valor.

Exemplos

Input:  nums = [4, 6, 10]
Output: 60
Por quê: 60 é o menor número divisível por 4, 6 e 10
Input:  nums = [12, 18, 24]
Output: 72
Por quê: os valores compartilham fatores, então a resposta fica bem abaixo do produto deles
Input:  nums = [9]
Output: 9
Por quê: edge case: um único ônibus encontra a si mesmo na primeira volta

Dicas

0 / 3

Tempo-alvo
O(n log(max(nums)))
Espaço-alvo
O(1)

Restrições

  • every value is a positive integer
  • the list holds at least one value

Travou na ideia, e não no código? MDC e Euclides explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado