Solution: Greatest Common Divisor
Solutions for the Greatest Common Divisor Problem.
We'll cover the following
Naive solution
Here is the simplest, but terribly slow, way to compute the greatest common divisor:
for d from min downto 1:
if d divides both a and b:
return d
For example, for a and b, this algorithm will perform about divisions.
Stop and think: If you computed a b, could you immediately find ab b?
A simple, but crucial idea, that will lead us to a much faster algorithm is suggested by the illustration below.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.