GCD of Two Numbers
Practice this coding question on Coding Gurukul.
Problem statement
Two ribbon rolls must be cut into equal whole-number lengths without leaving scraps. Find the largest piece length that works for both rolls. Your task Compute the greatest common divisor of the positive integers a and b. Important details The answer must divide both values exactly. It is the largest such positive divisor, not the smallest common multiple. Equal lengths have that length as their answer; coprime lengths have answer one. Apply the Euclidean algorithm, repeatedly reducing a pair with a remainder, to handle large inputs efficiently. Swapping the order of the two input lengths must not change the result. Worked example For lengths 48 and 18, pieces of length 6 divide both rolls. No larger length does, so print 6.
Input format
One line contains a and b.
Output format
Print gcd(a, b).
Constraints
1 <= a, b <= 1000000000.
Sample input
48 18
Sample output
6
Sign in to run or submit a solution in C++, Java or Python.