Foundations Working with digits and divisors
35. GCD of Two Numbers
You are given two positive integers a and b. Return their greatest common divisor (GCD): the
largest integer that divides both of them with no remainder.
For example, the numbers that divide both 20 and 30 are 1, 2, 5 and 10. The largest of them is 10, so the GCD of 20 and 30 is 10.
Example 1
Input: a = 84, b = 36
12Explanation: The numbers that divide both 84 and 36 are 1, 2, 3, 4, 6 and 12. The largest is 12.
Example 2
Input: a = 9, b = 45
9Explanation: 9 divides 45 exactly (45 = 9 × 5), and nothing larger than 9 can divide 9. So the answer is 9 itself.
Example 3
Input: a = 1000000000000000, b = 999999999999999
1Explanation: These are two numbers in a row. A number that divides both would also divide their difference, 1, so only 1 divides both.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ a, b ≤ 1015
Clarifying questions
What you would ask an interviewer before writing any code.