Array ( [0] => [1] => questions [2] => HackwithInfy-Previous-Questions [3] => EUCLIDIAN-GCD-ALGORITHM )
Given two Integers. Find the GCD of the integers using Euclidian GCD Algorithm.
2 integers separated by spaces.
Print the Greatest Common Divisor.
20 30
5
21 31
1
788 488
4
Login to see Discussion
Step-i) Let a, b be the two numbers
Step-ii) a mod b = R
Step-iii) Let a = b and b = R
Step-iv) Repeat Steps 2 and 3 until a mod b is greater than 0
Step-v) GCD = b
Time Complexity: O(log n)
Space Complexity: O(1)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution