Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Menor múltiplo comum de um intervalo

Encontre o menor número positivo que é divisível por todos os inteiros de um intervalo.

O que você vai aprender

  • Calcular o mmc(a, b) a partir do mdc(a, b)
  • Acumular uma operação ao longo de um intervalo de números
  • Evitar overflow nos valores intermediários

Problema

Ver original (inglês)

Uma padaria embala biscoitos em caixas de todos os tamanhos de lo a hi. Ela quer uma única quantidade por fornada que encha caixas de qualquer um desses tamanhos sem sobrar nada. A resposta é o menor número positivo divisível por todos os inteiros de lo a hi, ou seja, o mínimo múltiplo comum (MMC) deles.

Implemente smallest_multiple(lo, hi).

Entrada

lo: o menor tamanho de caixa.

hi: o maior tamanho de caixa.

Saída

Retorne o menor inteiro positivo que é divisível, sem resto, por cada um de lo, lo + 1, ..., hi.

Restrições

1 ≤ lo ≤ hi ≤ 40 (a resposta cabe em um inteiro de 64 bits com sinal)

Exemplos

Exemplo 1
Entrada:
lo = 1
hi = 6

Saída esperada:
expected = 60
Entrada:
long long lo = 1;
long long hi = 6;

Saída esperada:
long long expected = 60;
Entrada:
long lo = 1;
long hi = 6;

Saída esperada:
long expected = 60;

Explicação

60 é divisível por 1, 2, 3, 4, 5 e 6, e nenhum número positivo menor é, então a resposta é 60.

Exemplo 2
Entrada:
lo = 4
hi = 6

Saída esperada:
expected = 60
Entrada:
long long lo = 4;
long long hi = 6;

Saída esperada:
long long expected = 60;
Entrada:
long lo = 4;
long hi = 6;

Saída esperada:
long expected = 60;

Explicação

mmc(4, 5) = 20 e mmc(20, 6) = 60, então a resposta é 60 de novo: os tamanhos pequenos não acrescentaram nada.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

O mmc de um intervalo inteiro pode ser construído um número de cada vez.

Dica 2

mmc(a, b) = a / mdc(a, b) × b.

Dica 3

Divida antes de multiplicar, para que o valor intermediário nunca fique maior que a resposta.

Complexidade esperada

tempo O(n log M), espaço extra O(1)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.