re:re:actable
Урок 104 минуты чтения

Какие математические приемы нужны в алгоритмах?

На этой странице
Кратко

Для 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!.

Документация

cp-algorithms: Euclidean algorithm, MDN: BigInt.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам