The Maths You Actually Need

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.

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]

The division-first ordering in lcm is deliberate: a * b can exceed the safe integer range for inputs that a / gcd * b handles comfortably.

Primes with a sieve

Testing one number for primality is a loop to its square root. Listing every prime below n is far better done with the Sieve of Eratosthenes - cross out multiples of each prime and whatever survives is prime, in roughly O(n log log n).

function isPrime(n) {
  if (n < 2) return false
  if (n % 2 === 0) return n === 2
  for (let i = 3; i * i <= n; i += 2) {
    if (n % i === 0) return false
  }
  return true
}

function primesUpTo(n) {
  const sieve = new Array(n + 1).fill(true)
  sieve[0] = sieve[1] = false

  for (let i = 2; i * i <= n; i++) {
    if (!sieve[i]) continue
    // Start at i*i — smaller multiples already have a smaller factor.
    for (let j = i * i; j <= n; j += i) sieve[j] = false
  }

  return sieve.flatMap((prime, value) => (prime ? [value] : []))
}

console.log(primesUpTo(30))  // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Modulo, and the negative-number trap

JavaScript's % is a remainder, not a mathematical modulo: -1 % 5 is -1, not 4. Any time an index can go negative - rotating an array, wrapping around a circular buffer - you need the corrected form.

const mod = (n, m) => ((n % m) + m) % m

console.log(-1 % 5)        // -1  — usually not what you want
console.log(mod(-1, 5))    // 4

// Rotating an array right by k, with k possibly larger than the length.
function rotate(items, k) {
  const n = items.length
  const shift = mod(k, n)
  return [...items.slice(n - shift), ...items.slice(0, n - shift)]
}

console.log(rotate([1, 2, 3, 4, 5], 2))   // [4, 5, 1, 2, 3]
console.log(rotate([1, 2, 3, 4, 5], -1))  // [2, 3, 4, 5, 1]

Integer limits

• Safe integers stop at 2⁵³ − 1 - Number.MAX_SAFE_INTEGER. Beyond that, addition silently loses precision.
• Bitwise operators truncate to 32 bits, a much lower ceiling than the above.
• Use BigInt when a problem says results may be large, or when it asks for an answer modulo 10⁹ + 7 and intermediate products would overflow.

That modulus, 10⁹ + 7, appears constantly in competitive problems for two reasons: it is prime, which keeps modular division well defined, and it is small enough that the product of any two values below it stays inside the 64-bit range most languages use. JavaScript's 53-bit safe range is narrower, so multiplying two numbers near the modulus needs BigInt even though the final answer fits comfortably.

Counting without enumerating

A few combinatorial facts save whole problems. The number of ways to choose k items from n is n! / (k! · (n − k)!), a set of n elements has 2ⁿ subsets, and n distinct items arrange in n! orders. Recognising that a question is asking for one of these turns an intractable enumeration into a single formula - and the 2ⁿ figure is exactly the bound that tells you when bitmask techniques stay affordable.