|
Be the first user to complete this post
|
Add to List |
109. Find Greatest Common Divisor (GCD) Efficiently with Euclidean Algorithm
The greatest common divisor (GCD) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 10 and 15 is 5. (Source - Wiki - http://en.wikipedia.org/wiki/Greatest_common_divisor).
Euclidean Algorithm : The greatest common divisor of two numbers remains the same if the larger number is replaced by its difference with the smaller number. If we keep repeat this process until one of the number becomes 0, then other number will be the GCD. We can solve this recursively.
Example:
GCD of 282 and 156 will be the same as 156 and (282-156)=126. GCD of 156 and 126 will be the same as 126 and (156-126) = 30 GCD of 126 and 30 will be the same as 18 and (126-30) = 96 GCD of 96 and 30 will be the same as 30 and (96-30) = 66 GCD of 66 and 30 will be the same as 30 and (66-30) = 36 GCD of 36 and 30 will be the same as 30 and (36-30) = 6 GCD of 6 and 30 will be the same as 6 and (30-6) = 24 GCD of 24 and 6 will be the same as 6 and (24-6) = 18 GCD of 6 and 18 will be the same as 6 and (18-6) = 12 GCD of 12 and 6 will be the same as 6 and (12-6) = 6 GCD of 6 and 6 will be the same as 6 and (6-6) = 0 one number becomes 0, other number 6 will be the GCD.
Output:
6