Tous les défis
Facile 1 résolu 50.0 % de réussite

Greatest Common Divisor

Find the largest number that divides both values.

Ce que vous allez apprendre

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

Problème

Afficher la traduction

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.

Contraintes

0 ≤ a, b ≤ 10¹⁸

Exemples

Exemple 1
Entrée :
a = 48
b = 18

Sortie attendue :
expected = 6
Entrée :
long long a = 48;
long long b = 18;

Sortie attendue :
long long expected = 6;
Entrée :
long a = 48;
long b = 18;

Sortie attendue :
long expected = 6;

Explication

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

Exemple 2
Entrée :
a = 17
b = 5

Sortie attendue :
expected = 1
Entrée :
long long a = 17;
long long b = 5;

Sortie attendue :
long long expected = 1;
Entrée :
long a = 17;
long b = 5;

Sortie attendue :
long expected = 1;

Explication

17 and 5 share no factor other than 1.

Comment l'aborder

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

Indice 1

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

Indice 2

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

Indice 3

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

Complexité attendue

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

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.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 HJhettory Jurash Python 970 ms - 3/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.