Greatest Common Divisor
This problem was taken from the Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 2, that I’ve recently completed. If you are taking that course or plan to take that course, please don’t look ahead at the solution as it will be against the Honor Code and won’t do you any good.
Problem Introduction
The greatest common divisor GCD(a,b) of two non-negative integers a and b (which are not both equal to 0) is the greatest integer d that divides both a and b.
Problem Description
Task: Given two integers a and b, find their greatest common divisor.
Input Format: The two integers a, b are given in the same line separated by space.
Constraints: 1 ≤ a,b ≤ 2 ·10 ^9
Output Format: Output GCD(a,b).
Time Limits: C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit: 512 Mb
Sample 1
Input:
18 35
Output:
1
Sample 2
Input:
28851538 1183019
Output:
17657
My Solution:
Explanation:
Although the first function, gcd(a, b), gives the correct answer, we can’t use it because on larger inputs, like in Sample 2, it takes too long to compute the answer and we can’t fulfill the Time Limit constraint, i-e 1 sec.
Therefore, we use a more complex but faster algorithm, euclidGCD(a,b). If you want to understand this algorithm and see how and why it works, here is a nice explanation at Khan Academy.
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.
