Problema
Una panadería empaca galletas en cajas de todos los tamaños, desde lo hasta hi. Quiere hornear una tanda con la que pueda llenar cajas de cualquiera de esos tamaños sin que sobre ninguna galleta. La respuesta es el menor número positivo divisible por todos los enteros de lo a hi, es decir, su mínimo común múltiplo.
Implementa smallest_multiple(lo, hi).
Entrada
lo: el tamaño de caja más pequeño.
hi: el tamaño de caja más grande.
Salida
Devuelve el menor entero positivo que se puede dividir sin resto entre cada uno de lo, lo + 1, ..., hi.
Restricciones
1 ≤ lo ≤ hi ≤ 40 (la respuesta cabe en un entero de 64 bits con signo)
Ejemplos
Entrada:
lo = 1
hi = 6
Salida esperada:
expected = 60
Entrada:
long long lo = 1;
long long hi = 6;
Salida esperada:
long long expected = 60;
Entrada:
long lo = 1;
long hi = 6;
Salida esperada:
long expected = 60;
Explicación
60 es divisible entre 1, 2, 3, 4, 5 y 6, y ningún número positivo menor lo es, así que la respuesta es 60.
Entrada:
lo = 4
hi = 6
Salida esperada:
expected = 60
Entrada:
long long lo = 4;
long long hi = 6;
Salida esperada:
long long expected = 60;
Entrada:
long lo = 4;
long hi = 6;
Salida esperada:
long expected = 60;
Explicación
mcm(4, 5) = 20 y mcm(20, 6) = 60, así que la respuesta vuelve a ser 60: los tamaños pequeños no aportaban nada.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
El mcm de todo un intervalo se puede construir número a número.
Pista 2
mcm(a, b) = a / mcd(a, b) × b.
Pista 3
Divide antes de multiplicar para que el valor intermedio nunca supere la respuesta.
Complejidad esperada
tiempo O(n log M), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.