Greatest common divisor
Reducing a fraction, or laying tiles that divide a wall evenly, both come down to the same number.
- Signs do not matter: the divisor of -12 and 18 is the same as of 12 and 18.
- The divisor of 0 and n is n; of 0 and 0 it is 0.
greatestCommonDivisor(first: int, second: int) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func greatestCommonDivisor(first int, second int) int {
}Worked examples
| Call | Result |
|---|---|
greatestCommonDivisor(12, 18) | 6 |
greatestCommonDivisor(17, 5) | 1 |
greatestCommonDivisor(0, 5) | 5 |
greatestCommonDivisor(0, 0) | 0 |
Hint
Euclid: keep replacing the pair with (second, first mod second) until the second is zero.
Reference solution in Go
func greatestCommonDivisor(first int, second int) int {
a, b := first, second
if a < 0 {
a = -a
}
if b < 0 {
b = -b
}
for b != 0 {
a, b = b, a%b
}
return a
}