Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Kleinstes gemeinsames Vielfaches eines Bereichs

Finde die kleinste positive Zahl, die durch jede ganze Zahl eines Bereichs ohne Rest teilbar ist.

Das lernst du

  • kgV(a, b) aus ggT(a, b) berechnen
  • Eine Operation schrittweise über einen Zahlenbereich anwenden
  • Zwischenwerte vor einem Überlauf bewahren

Problem

Eine Bäckerei packt Kekse in Schachteln aller Größen von lo bis hi. Sie sucht eine Keksmenge, mit der sich Schachteln jeder dieser Größen restlos füllen lassen. Gesucht ist also die kleinste positive Zahl, die durch jede ganze Zahl von lo bis hi teilbar ist, das kleinste gemeinsame Vielfache (kgV) dieser Zahlen.

Implementiere smallest_multiple(lo, hi).

Eingabe

lo: Die kleinste Schachtelgröße.

hi: Die größte Schachtelgröße.

Ausgabe

Gib die kleinste positive ganze Zahl zurück, die durch jede der Zahlen lo, lo + 1, ..., hi ohne Rest teilbar ist.

Einschränkungen

1 ≤ lo ≤ hi ≤ 40 (das Ergebnis passt in eine vorzeichenbehaftete 64-Bit-Ganzzahl)

Beispiele

Beispiel 1
Eingabe:
lo = 1
hi = 6

Erwartete Ausgabe:
expected = 60
Eingabe:
long long lo = 1;
long long hi = 6;

Erwartete Ausgabe:
long long expected = 60;
Eingabe:
long lo = 1;
long hi = 6;

Erwartete Ausgabe:
long expected = 60;

Erläuterung

60 ist durch 1, 2, 3, 4, 5 und 6 teilbar, und keine kleinere positive Zahl ist es, also lautet die Antwort 60.

Beispiel 2
Eingabe:
lo = 4
hi = 6

Erwartete Ausgabe:
expected = 60
Eingabe:
long long lo = 4;
long long hi = 6;

Erwartete Ausgabe:
long long expected = 60;
Eingabe:
long lo = 4;
long hi = 6;

Erwartete Ausgabe:
long expected = 60;

Erläuterung

kgV(4, 5) = 20 und kgV(20, 6) = 60, die Antwort ist also wieder 60. Die kleinen Größen ändern nichts.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Das kgV eines ganzen Bereichs lässt sich Zahl für Zahl aufbauen.

Hinweis 2

kgV(a, b) = a / ggT(a, b) × b.

Hinweis 3

Teile, bevor du multiplizierst, dann wird der Zwischenwert nie größer als das Ergebnis.

Erwartete Komplexität

Zeit O(n log M), zusätzlicher Speicher O(1)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.