Problems › TypeScript › warmup
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
Where you start
function greatestCommonDivisor(first: number, second: number): number {
}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 TypeScript
function greatestCommonDivisor(first: number, second: number): number {
let a = Math.abs(first);
let b = Math.abs(second);
while (b !== 0) [a, b] = [b, a % b];
return a;
}