Coding problem · Easy · Basics

Greatest Common Divisor

Easy Algorithms & data structures

Return the greatest common divisor (GCD) of two non-negative integers a and b (not both 0).

Example 1

Input: a = 48, b = 18
Output: 6

Example 2

Input: a = 7, b = 5
Output: 1

Hints

Hint 1

Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(log n) · Space O(1)

Replace (a, b) with (b, a % b) until b is 0; then a is the GCD. It's one of the oldest algorithms still in use, and very fast: O(log min(a, b)).

Reference solution

function gcd(a, b) {
  while (b !== 0) [a, b] = [b, a % b];
  return a;
}

function gcd(a: number, b: number): number {
  while (b !== 0) [a, b] = [b, a % b];
  return a;
}

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

<?php

function gcd(int $a, int $b): int
{
    while ($b !== 0) {
        [$a, $b] = [$b, $a % $b];
    }
    return $a;
}

class Solution {
    public int gcd(int a, int b) {
        while (b != 0) { int t = a % b; a = b; b = t; }
        return a;
    }
}

Was this page helpful?