3. Greatest Common Divisor (GCD)

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

3. Greatest Common Divisor (GCD)

Table of Contents

Contents are not accessible

Problem Statement

Write recursive code to calculate the Greatest Common Divisor (GCD) of Two Positive Numbers.

The greatest common divisor (GCD) of two positive integers A and B is the largest positive integer that divides both A and B without leaving a remainder.

Let's see some example inputs/outputs for this example:

Input(s)	Output(s)	Explanation
A = 12, B = 18	GCD = 6	The factors of 12 are [1, 2, 3, 4, 6, 12], and the factors of 18 are [1, 2, 3, 6, 9, 18]. The common factors between 12 and 18 are [1, 2, 3, 6], and the largest common factor is 6.
A = 25, B = 15	GCD = 5	The factors of 25 are [1, 5, 25], and the factors of 15 are [1, 3, 5, 15]. The common factors between 25 and 15 are [1, 5], and the largest common factor is 5.
A = 40, B = 60	GCD = 20	The factors of 40 are [1, 2, 4, 5, 8, 10, 20, 40], and the factors of 60 are [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]. The common factors between 40 and 60 are [1, 2, 4, 5, 10, 20], and the largest common factor is 20.

Try it yourself

Try solving this question here:

Code

Here is the code for this algorithm:

Python3

. . . .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible