Todos los desafíos
Fácil 0 resueltos 0% de aceptación

Mínimo múltiplo común de un intervalo

Encuentra el menor número positivo que es divisible por todos los enteros de un intervalo.

Lo que aprenderás

  • Calcular mcm(a, b) a partir de mcd(a, b)
  • Aplicar una operación acumulada sobre un intervalo de números
  • Evitar que los valores intermedios se desborden

Problema

Ver original (inglés)

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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.