Alle Herausforderungen
Einfach 1 gelöst 50.0% Erfolgsquote

Greatest Common Divisor

Find the largest number that divides both values.

Das lernst du

  • Apply Euclid's algorithm with remainders
  • Turn a math rule into a loop
  • Understand why the algorithm is fast

Problem

Übersetzung anzeigen

Return the greatest common divisor of a and b. Euclid's algorithm repeatedly replaces (a, b) with (b, a mod b) until b is 0.

Implement gcd(a, b).

Input

a: The first number. b: The second number.

Output

Return gcd(a, b). gcd(0, 0) is 0.

Einschränkungen

0 ≤ a, b ≤ 10¹⁸

Beispiele

Beispiel 1
Eingabe:
a = 48
b = 18

Erwartete Ausgabe:
expected = 6
Eingabe:
long long a = 48;
long long b = 18;

Erwartete Ausgabe:
long long expected = 6;
Eingabe:
long a = 48;
long b = 18;

Erwartete Ausgabe:
long expected = 6;

Erläuterung

48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the answer is 6.

Beispiel 2
Eingabe:
a = 17
b = 5

Erwartete Ausgabe:
expected = 1
Eingabe:
long long a = 17;
long long b = 5;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long a = 17;
long b = 5;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

17 and 5 share no factor other than 1.

So gehst du vor

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

Hinweis 1

The gcd does not change when you replace a pair with the remainder step.

Hinweis 2

Keep swapping the roles of the two numbers until the second becomes zero.

Hinweis 3

Be sure to handle the case where both inputs are zero.

Erwartete Komplexität

O(log min(a, b)) time, O(1) extra space

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.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 HJhettory Jurash Python 970 ms - 3/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.