Tous les défis
Facile 0 résolus 0 % de réussite

Plus petit multiple commun

Trouver le plus petit entier positif divisible par tous les entiers d'un intervalle.

Ce que vous allez apprendre

  • Calculer PPCM(a, b) à partir de PGCD(a, b)
  • Appliquer une opération de proche en proche sur un intervalle de nombres
  • Empêcher les valeurs intermédiaires de dépasser la capacité

Problème

Une boulangerie emballe ses biscuits dans des boîtes de toutes les tailles, de lo à hi. Elle cherche une taille de fournée qui remplisse exactement des boîtes de n'importe laquelle de ces tailles, sans reste. La réponse est le plus petit entier positif divisible par tous les entiers de lo à hi, autrement dit leur plus petit commun multiple (PPCM).

Implémentez smallest_multiple(lo, hi).

Entrée

lo : la plus petite taille de boîte.

hi : la plus grande taille de boîte.

Sortie

Renvoyez le plus petit entier strictement positif divisible sans reste par chacun des entiers lo, lo + 1, ..., hi.

Contraintes

1 ≤ lo ≤ hi ≤ 40 (la réponse tient dans un entier signé sur 64 bits)

Exemples

Exemple 1
Entrée :
lo = 1
hi = 6

Sortie attendue :
expected = 60
Entrée :
long long lo = 1;
long long hi = 6;

Sortie attendue :
long long expected = 60;
Entrée :
long lo = 1;
long hi = 6;

Sortie attendue :
long expected = 60;

Explication

60 est divisible par 1, 2, 3, 4, 5 et 6, et aucun entier positif plus petit ne l'est, donc la réponse est 60.

Exemple 2
Entrée :
lo = 4
hi = 6

Sortie attendue :
expected = 60
Entrée :
long long lo = 4;
long long hi = 6;

Sortie attendue :
long long expected = 60;
Entrée :
long lo = 4;
long hi = 6;

Sortie attendue :
long expected = 60;

Explication

PPCM(4, 5) = 20 et PPCM(20, 6) = 60, donc la réponse est encore 60 : les petites tailles n'apportaient rien.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Le PPCM de tout un intervalle se construit un nombre à la fois.

Indice 2

PPCM(a, b) = a / PGCD(a, b) × b.

Indice 3

Divisez avant de multiplier pour que la valeur intermédiaire ne dépasse jamais la réponse.

Complexité attendue

temps O(n log M), espace supplémentaire O(1)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.