Math for DSA
The Maths You Actually Need
Written by Swapnil RajaPublished
A handful of number-theory facts appear again and again. None of them is deep, and not knowing one costs an entire question.
GCD and LCM
The Euclidean algorithm finds the greatest common divisor by repeatedly replacing the larger number with the remainder. It runs in O(log min(a, b)) - fast enough to be free.
GCD, LCM, and simplifying fractions
javascript
function gcd(a, b) {
while (b !== 0) [a, b] = [b, a % b]
return Math.abs(a)
}
// Divide before multiplying so the intermediate value stays small.
function lcm(a, b) {
return Math.abs(a / gcd(a, b) * b)
}
function simplify(numerator, denominator) {
const divisor = gcd(numerator, denominator)
return [numerator / divisor, denominator / divisor]
}
console.log(gcd(48, 18)) // 6
console.log(lcm(4, 6)) // 12
console.log(simplify(84, 126)) // [2, 3]