gcd

Hard · Number Theory · 2 test cases

Given two numbers a and b, return the greatest common divisor (GCD) of a and b. The GCD is the largest positive integer that divides both a and b without leaving a remainder.

Examples

gcd(8, 12) → 4
gcd(14, 21) → 7

Starter code

function gcd(a, b) {

}

Complexity of the optimal solution

Time O(log(min(a,b))), space O(1). This solution uses the Euclidean algorithm. The number of steps is related to the number of digits in the smaller input number, resulting in a logarithmic time complexity. It uses constant extra space.

Solve gcd in the browser