Mínimo múltiplo comum de uma lista
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
Resolva primeiro para dois valores. O produto deles é sempre um múltiplo comum, mas conta duas vezes cada fator compartilhado.
Para dois valores a e b, o MMC é a vezes b dividido pelo MDC (GCD) deles, e o algoritmo de Euclides encontra esse divisor rapidamente.
Acumule ao longo da lista: mantenha uma resposta parcial que começa em 1 e combine-a com cada valor, um por vez, usando a fórmula de dois valores. Divida antes de multiplicar, para que os números intermediários continuem pequenos.
- 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
Solução
O mínimo múltiplo comum de dois números é o produto deles dividido pelo máximo divisor comum, porque o divisor é exatamente a parte com que os dois números contribuem, e o produto a conta duas vezes. A operação é associativa, então a resposta para a lista inteira é construída combinando os valores, um de cada vez, em um resultado acumulado. Dividir o resultado acumulado pelo divisor antes de multiplicar mantém todo valor intermediário não maior que a resposta final. Cada passo custa uma chamada de Euclides, então o tempo é O(n log M), para o maior valor M, e o espaço é 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])) # -> 30030Travou na ideia, e não no código? MDC e Euclides explica isso.