Solution Review: Greatest Common Divisor

Let’s take a detailed look at the previous challenge’s solution.


There are many ways to find the GCD of two integers. We’ll use Euclid’s algorithm to calculate the GCD:

  • If n = 0 then GCD(n, m) = m. This is a termination condition.

  • If m = 0 then GCD(n, m) = n. This is a termination condition.

  • Write n in the form of a quotient remainder (n=mq+r)(n = mq + r). q is the quotient, and r is the remainder.

  • Since GCD(N,M) = GCD(M,R), use the Euclidean Algorithm to find GCD(M,R).

Coding exercise

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.