If the smaller of the two numbers can divide the larger number then the GCD is the smaller number.Įxplanation: Integers 1, 2, 4, and 8 can divide both 40 and 30.When both m and n are 0, their GCD is undefined i.e.Similarly, if m != 0, n = 0, then GCD(m, n) = m. It means, if m = 0, n != 0, then GCD(m, n) = n. If any one of the integer is 0, then the GCD is the other number.It is the largest number which is a divisor of both m and n. Given two non-negative integers m and n, we have to find their greatest common divisor or GCD or HCF. It allows computers to do various simple number-theoretic tasks and serves as a foundation for more complicated algorithms in number theory.One of the best problems to learn problem-solving using recursion (Decrease and conquer strategy).
It is a method of computing the greatest common divisor (GCD) of two integers m and n. The Euclidean algorithm is one of the oldest and most widely known algorithms.Difficulty: Medium, Asked-in: Microsoft, SAP Labs
