Какие математические приемы нужны в алгоритмах?
На этой странице
Для frontend/backend собеседований не нужна олимпиадная математика с нуля, но полезно знать делимость, остаток, gcd, простые числа, modulo arithmetic и базовую комбинаторику.
Вопрос
Какие математические приемы чаще всего нужны в алгоритмических задачах?
Остаток от деления
Оператор % возвращает остаток.
console.log(10 % 3) // 1
console.log(12 % 4) // 0Кейсы:
- четность:
num % 2 === 0; - циклический индекс;
- hash bucket;
- modulo для больших чисел;
- группировка по остаткам.
Осторожно с отрицательными числами в JS
console.log(-1 % 5) // -1Если нужен всегда положительный modulo:
function mod(value: number, m: number): number {
return ((value % m) + m) % m
}GCD
GCD, greatest common divisor, - наибольший общий делитель.
Алгоритм Евклида:
function gcd(a: number, b: number): number {
a = Math.abs(a)
b = Math.abs(b)
while (b !== 0) {
const remainder = a % b
a = b
b = remainder
}
return a
}Пример:
gcd(12, 18) // 6Сложность:
O(log min(a, b))Где нужен:
- дроби;
- периоды;
- шаги по кругу;
- проверка возможности дойти с шагом;
- задачи на решетку.
LCM
LCM, least common multiple, - наименьшее общее кратное.
function lcm(a: number, b: number): number {
return Math.abs(a / gcd(a, b) * b)
}Сначала делим на gcd, чтобы уменьшить риск переполнения.
Простые числа
Простое число делится только на 1 и на само себя.
Проверка одного числа:
function isPrime(num: number): boolean {
if (num < 2) return false
for (let divisor = 2; divisor * divisor <= num; divisor++) {
if (num % divisor === 0) return false
}
return true
}Почему до sqrt(num):
если у числа есть делитель больше sqrt(num),
то парный делитель меньше sqrt(num)Sieve of Eratosthenes
Если нужно найти все простые до n:
function primesUpTo(n: number): number[] {
const isPrime = new Array(n + 1).fill(true)
isPrime[0] = false
isPrime[1] = false
for (let p = 2; p * p <= n; p++) {
if (!isPrime[p]) continue
for (let multiple = p * p; multiple <= n; multiple += p) {
isPrime[multiple] = false
}
}
const result: number[] = []
for (let i = 2; i <= n; i++) {
if (isPrime[i]) result.push(i)
}
return result
}Сложность:
O(n log log n)Подсчет делителей
function divisors(num: number): number[] {
const result: number[] = []
for (let divisor = 1; divisor * divisor <= num; divisor++) {
if (num % divisor !== 0) continue
result.push(divisor)
if (divisor !== num / divisor) {
result.push(num / divisor)
}
}
return result.sort((a, b) => a - b)
}Идея такая же: делители идут парами.
Modulo для больших ответов
В задачах часто пишут:
return answer modulo 1_000_000_007Тогда после каждой операции делаем % MOD.
const MOD = 1_000_000_007
function addMod(a: number, b: number): number {
return (a + b) % MOD
}Для больших произведений в JS может понадобиться BigInt.
const MOD = 1_000_000_007n
function multiplyMod(a: bigint, b: bigint): bigint {
return (a * b) % MOD
}Комбинаторика на базовом уровне
Нужно понимать разницу:
| Тема | Идея |
|---|---|
| Permutations | порядок важен |
| Combinations | порядок не важен |
| Subsets | взять или не взять каждый элемент |
| Cartesian product | все пары/наборы из нескольких множеств |
Пример:
[1, 2, 3]
subsets -> 2^3 = 8
permutations -> 3! = 6Что важно помнить: частые ошибки
- Забывать, что
%для отрицательных чисел в JS может быть отрицательным. - Проверять простоту до
n, а не доsqrt(n). - Начинать sieve с
2 * p, хотя можно сp * p. - Делать
a * bв number, когда может понадобитьсяBigInt. - Путать permutation и combination.
- Забывать
num < 2для prime check.
Что отвечать на собеседовании?
Для алгоритмов полезно знать modulo, gcd через алгоритм Евклида, lcm, проверку простоты до sqrt(n), sieve для множества простых чисел, делители парами и базовую комбинаторику: permutations, combinations, subsets. В JavaScript нужно помнить, что % с отрицательными числами возвращает отрицательный остаток, а для больших произведений может понадобиться BigInt.
Мини-шпаргалка
a % b- остаток.- Positive modulo:
((x % m) + m) % m. gcd- алгоритм Евклида.lcm(a, b) = abs(a / gcd(a, b) * b).- Prime check - до
sqrt(n). - Sieve - все простые до
n. - Subsets -
2^n. - Permutations -
n!.