Basic Maths for DSA

A little maths, a lot less work

You do not need advanced maths for coding interviews. You need about six small facts. Each one turns a slow loop into a fast loop. Lesson 12 gave you the words to measure this. Checking every number up to n is O(n) (the work grows in step with n). With the right fact, the same job becomes O(√n) or O(log n), which is much less work.

You met some of these ideas briefly in Lessons 4, 5 and 7: the prime check, the GCD loop, the sieve and fast power. This lesson explains why they work and what they cost. Then you can rebuild them from understanding, not from memory.

Digit problems revisited

Lesson 5's digit loop takes a number apart. The remainder operator % gives what is left after a division, so n % 10 is the last digit (for example, 4072 % 10 is 2). Math.floor(n / 10) divides by 10 and drops the decimal part, which removes that last digit. Two new observations:

• It is O(log n). Each pass removes one digit. A number n has about log₁₀ n digits (log₁₀ n means: how many times you can divide n by 10). Even n = 10¹⁸ needs only 19 passes.
• 10 is not special. Replace 10 with 2 and the same loop gives the binary digits. Binary is the way computers write numbers, using only 0 and 1. A single 0 or 1 is called a bit. You will read bits this way in Lesson 58.

function digitsOf(n, base = 10) {  if (n === 0) return [0];  const digits = [];  while (n > 0) {    digits.push(n % base);          // last digit    n = Math.floor(n / base);       // remove it  }  return digits.reverse();          // they came out last-first}console.log(digitsOf(4072));        // [ 4, 0, 7, 2 ]console.log(digitsOf(13, 2));       // [ 1, 1, 0, 1 ]   13 in binary

All divisors in √n steps

A divisor of n is a whole number that divides n with remainder 0. For example, the divisors of 6 are 1, 2, 3 and 6. The obvious way to find them all is to try every number from 1 to n. That is O(n). But divisors come in pairs: if i divides n, so does n / i.

function divisors(n) {  const small = [];  const large = [];  for (let i = 1; i * i <= n; i++) {    if (n % i === 0) {      small.push(i);                     // the small half of the pair      if (i !== n / i) large.push(n / i);  // its partner (skip 6 × 6 twice)    }  }  return [...small, ...large.reverse()];}console.log(divisors(36)); // [ 1, 2, 3, 4, 6, 9, 12, 18, 36 ]console.log(divisors(13)); // [ 1, 13 ]

The √n (square root of n) is the number that gives n when you multiply it by itself. For example, √36 = 6. The loop condition i * i <= n means “i ≤ √n”. It avoids Math.sqrt and its rounding. For n = 10¹², that is 10⁶ passes instead of 10¹². This is the difference between an instant answer and several hours.

Checking for a prime

A prime number is a whole number greater than 1 that has no divisors except 1 and itself. For example, 7 is prime, and 8 is not (2 divides it). The pairs idea gives a fast check. If n has any divisor other than 1 and n, the smaller number of its pair is at most √n. So if nothing up to √n divides n, then nothing does.

function isPrime(n) {  if (n < 2) return false;                 // 0 and 1 are not prime  for (let i = 2; i * i <= n; i++) {    if (n % i === 0) return false;         // found a divisor  }  return true;}console.log(isPrime(97));  // trueconsole.log(isPrime(91));  // false   (7 × 13)console.log(isPrime(1));   // false

Time O(√n), space O(1) (it needs no extra memory). Remember the edge cases: 0 and 1 are not prime, and 2 is the only even prime.

The Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm that finds all prime numbers up to n. To find every prime up to n, checking each number separately costs about n × √n. The sieve does better by working the other way round. It does not ask “is this number prime?”. Instead, it crosses out every number that is not prime, like a sieve (a kitchen strainer) that lets only the primes through. A multiple of i is any number you get by multiplying i by a whole number: 3, 6, 9, 12 are multiples of 3.

1. Start with every number from 2 to n marked as prime.
2. Take the smallest number still marked. It is prime. Cross out all its multiples.
3. Repeat. Stop once i × i is greater than n — every number left is prime.

Why start crossing at i * i? Smaller multiples of i, like 2 × 5 and 3 × 5 (when i is 5), were already crossed out by 2 and 3. And why stop at √n? Any non-prime number up to n has a divisor that is at most √n, so it has already been crossed out.

function primesUpTo(n) {  const isPrime = new Array(n + 1).fill(true);  isPrime[0] = false;  isPrime[1] = false;  for (let i = 2; i * i <= n; i++) {    if (!isPrime[i]) continue;               // already crossed out    for (let j = i * i; j <= n; j += i) {      isPrime[j] = false;                    // cross out multiples of i    }  }  const primes = [];  for (let i = 2; i <= n; i++) if (isPrime[i]) primes.push(i);  return primes;}console.log(primesUpTo(30)); // [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]

The sieve runs in about O(n log log n) time. This is so close to O(n) that you can treat it as linear. It uses O(n) space for the array. It is the standard answer whenever a problem needs many primes, for example “count the primes below 5,000,000”.

GCD with Euclid's algorithm

The GCD (greatest common divisor) of two numbers is the largest number that divides both: gcd(12, 18) = 6. You can try every candidate from the smaller number downwards. That works, but it is O(min(a, b)). Euclid (a Greek mathematician) found a much faster way more than 2,000 years ago. Euclid's algorithm finds the GCD by replacing the pair (a, b) with the smaller pair (b, a % b) again and again:

Traced: gcd(252, 105)

▶function gcd(a, b) {2  while (b !== 0) {3    const r = a % b;4    a = b;5    b = r;6  }7  return a;8}9console.log(gcd(252, 105));

The remainder becomes at most half as big every two steps. So Euclid's algorithm is O(log min(a, b)). For numbers around a billion, that is a few dozen passes at most.

LCM from the GCD

The LCM (least common multiple) is the smallest positive number that both a and b divide: lcm(4, 6) = 12. It comes straight from the GCD, because gcd(a, b) × lcm(a, b) = a × b. So lcm(a, b) = a × b / gcd(a, b).

function gcd(a, b) {  while (b !== 0) [a, b] = [b, a % b];  return a;}function lcm(a, b) {  return (a / gcd(a, b)) * b;        // divide first so the number stays small}console.log(gcd(12, 18));  // 6console.log(lcm(4, 6));    // 12console.log(lcm(21, 6));   // 42

For more than two numbers, apply the function to one pair at a time: gcd(a, b, c) = gcd(gcd(a, b), c), and the same for the LCM. In JavaScript you can do this with one reduce (an array method that folds a list into one value).

Remainders and modular arithmetic

Many problems count something enormous, such as the number of paths in a grid or the number of arrangements of a string. They then say “return the answer modulo 10⁹ + 7”. The remainder is what is left after a division: 17 divided by 5 is 3 with remainder 2. Modulo means “give me that remainder”. So the problem wants only the remainder after dividing by 1,000,000,007. Working only with remainders is called modular arithmetic. It follows these rules:

const M = 1_000_000_007;// Addition and multiplication: take % as often as you like(a + b) % M  ===  ((a % M) + (b % M)) % M(a * b) % M  ===  ((a % M) * (b % M)) % M// Subtraction: add M before the final % so the result is never negative(a - b) % M  →  ((a % M) - (b % M) + M) % M

So you can take % M after every addition or multiplication, and the numbers never grow large. Watch two details that are specific to JavaScript:

1. Negative numbers. In JavaScript, the % operator gives a result with the same sign as the left number. So a negative number gives a negative remainder:

console.log(7 % 3);              // 1console.log(-7 % 3);             // -1   JavaScript keeps the sign of the left sideconsole.log(((-7 % 3) + 3) % 3); // 2    the mathematical remainder

2. Multiplying two large remainders. A normal JavaScript number is stored as a 64-bit decimal (floating-point) value. It is exact for whole numbers only up to 2⁵³ ≈ 9 × 10¹⁵. Two remainders near 10⁹ multiply to about 10¹⁸, which is past that limit. The result silently loses its last digits. Use BigInt for those multiplications. BigInt is a JavaScript type for whole numbers of any size, and you write one with an n at the end, like 12n:

const M = 1_000_000_007;// Wrong: the product is about 1.2 × 10^17, beyond the safe limit of 2^53 ≈ 9 × 10^15console.log((123456789 * 987654321) % M);                         // 259106854// Right: BigInt keeps every digitconsole.log(Number((123456789n * 987654321n) % BigInt(M)));       // 259106859

Fast exponentiation

xⁿ means x multiplied by itself n times (the exponent n says how many). Doing that with n multiplications is O(n). Fast exponentiation (also called exponentiation by squaring) is a method that finds xⁿ with only about log n multiplications. It uses the fact that squaring doubles the exponent: x → x² → x⁴ → x⁸. Any n can be written as a sum of these powers of two. Those are its binary digits. For 13 = 8 + 4 + 1 (binary 1101):

3¹³ = 3⁸ × 3⁴ × 3¹

So walk through the bits of n with the digit loop (base 2). Keep squaring x. Whenever the current bit is 1, multiply the current x into the result.

function power(x, n) {  let result = 1;  while (n > 0) {    if (n % 2 === 1) result *= x;   // this bit of n is 1: include the current x    x *= x;                         // x, x², x⁴, x⁸ …    n = Math.floor(n / 2);          // move to the next bit  }  return result;}console.log(power(3, 13));  // 1594323console.log(power(2, 10));  // 1024

In real problems, fast power is almost always used together with a modulus, for example (2^{1,000,000,000}) % (10⁹ + 7). Practice question 7 builds that version, with BigInt.

The costs side by side

Practice questions

Before each solution, read the constraints (the limits on the input size) and use the table from Lesson 12 to decide which growth rate is fast enough. Most of these questions are about choosing the right fact.

function findGCD(nums) {  const lo = Math.min(...nums);  const hi = Math.max(...nums);  for (let d = lo; d >= 1; d--) {    if (lo % d === 0 && hi % d === 0) return d;  }}console.log(findGCD([2, 5, 6, 9, 10])); // 2console.log(findGCD([7, 5, 6, 8, 3]));  // 1

function gcd(a, b) {  while (b !== 0) [a, b] = [b, a % b];  return a;}function findGCD(nums) {  return gcd(Math.min(...nums), Math.max(...nums));}console.log(findGCD([2, 5, 6, 9, 10])); // 2console.log(findGCD([7, 5, 6, 8, 3]));  // 1console.log(findGCD([3, 3]));           // 3

function smallestMultiple(n) {  for (let x = n; ; x += n) {    let ok = true;    for (let d = 1; d <= n; d++) {      if (x % d !== 0) { ok = false; break; }    }    if (ok) return x;  }}console.log(smallestMultiple(4));  // 12console.log(smallestMultiple(10)); // 2520

function gcd(a, b) {  while (b !== 0) [a, b] = [b, a % b];  return a;}function smallestMultiple(n) {  let result = 1;  for (let k = 2; k <= n; k++) {    result = (result / gcd(result, k)) * k;  }  return result;}console.log(smallestMultiple(4));  // 12console.log(smallestMultiple(10)); // 2520console.log(smallestMultiple(20)); // 232792560

function isThree(n) {  let count = 0;  for (let i = 1; i * i <= n; i++) {    if (n % i === 0) count += i * i === n ? 1 : 2;  }  return count === 3;}console.log(isThree(2));  // falseconsole.log(isThree(4));  // trueconsole.log(isThree(12)); // false

function isPrime(n) {  if (n < 2) return false;  for (let i = 2; i * i <= n; i++) if (n % i === 0) return false;  return true;}function isThree(n) {  const r = Math.round(Math.sqrt(n));  return r * r === n && isPrime(r);}console.log(isThree(4));  // trueconsole.log(isThree(9));  // trueconsole.log(isThree(16)); // false   (1, 2, 4, 8, 16)

function digitSquareSum(n) {  let sum = 0;  while (n > 0) {    const d = n % 10;    sum += d * d;    n = Math.floor(n / 10);  }  return sum;}function isHappy(n) {  const seen = new Set();  while (n !== 1 && !seen.has(n)) {    seen.add(n);    n = digitSquareSum(n);  }  return n === 1;}console.log(isHappy(19)); // trueconsole.log(isHappy(2));  // false

function digitSquareSum(n) {  let sum = 0;  for (; n > 0; n = Math.floor(n / 10)) sum += (n % 10) ** 2;  return sum;}function isHappy(n) {  let slow = n;  let fast = digitSquareSum(n);  while (fast !== 1 && slow !== fast) {    slow = digitSquareSum(slow);    fast = digitSquareSum(digitSquareSum(fast));  }  return fast === 1;}console.log(isHappy(19)); // trueconsole.log(isHappy(2));  // false

function isUgly(n) {  if (n <= 0) return false;  for (const p of [2, 3, 5]) {    while (n % p === 0) n /= p;  }  return n === 1;}console.log(isUgly(6));  // trueconsole.log(isUgly(1));  // trueconsole.log(isUgly(14)); // falseconsole.log(isUgly(0));  // false

function primeFactors(n) {  const factors = [];  for (let d = 2; d * d <= n; d++) {    while (n % d === 0) {      factors.push(d);      n /= d;    }  }  if (n > 1) factors.push(n);   // what is left is prime  return factors;}console.log(primeFactors(360));        // [ 2, 2, 2, 3, 3, 5 ]console.log(primeFactors(97));         // [ 97 ]console.log(primeFactors(1000000007)); // [ 1000000007 ]

const M = 1_000_000_007;function powMod(a, b) {  let result = 1;  a %= M;  while (b > 0) {    if (b % 2 === 1) result = (result * a) % M;    a = (a * a) % M;    b = Math.floor(b / 2);  }  return result;}console.log(powMod(2, 10));  // 1024        correct (small numbers)console.log(powMod(2, 100)); // 976371253   wrong — the right answer is 976371285

const M = 1_000_000_007n;function powMod(a, b) {  let base = BigInt(a) % M;  let exp = BigInt(b);  let result = 1n;  while (exp > 0n) {    if (exp % 2n === 1n) result = (result * base) % M;    base = (base * base) % M;    exp = exp / 2n;              // BigInt division already rounds down  }  return Number(result);}console.log(powMod(2, 10));         // 1024console.log(powMod(2, 100));        // 976371285console.log(powMod(3, 200));        // 136318165console.log(powMod(2, 1000000000)); // 140625001

function myPow(x, n) {  let result = 1;  for (let i = 0; i < Math.abs(n); i++) result *= x;  return n < 0 ? 1 / result : result;}console.log(myPow(2, 10)); // 1024console.log(myPow(2, -2)); // 0.25

function myPow(x, n) {  if (n < 0) {    x = 1 / x;    n = -n;  }  let result = 1;  while (n > 0) {    if (n % 2 === 1) result *= x;    x *= x;    n = Math.floor(n / 2);  }  return result;}console.log(myPow(2, 10)); // 1024console.log(myPow(2, -2)); // 0.25console.log(myPow(3, 13)); // 1594323

function isPrime(n) {  if (n < 2) return false;  for (let i = 2; i * i <= n; i++) if (n % i === 0) return false;  return true;}function closestPrimes(left, right) {  let prev = -1;  let best = [-1, -1];  for (let k = left; k <= right; k++) {    if (!isPrime(k)) continue;    if (prev !== -1 && (best[0] === -1 || k - prev < best[1] - best[0])) best = [prev, k];    prev = k;  }  return best;}console.log(closestPrimes(10, 19)); // [ 11, 13 ]console.log(closestPrimes(4, 6));   // [ -1, -1 ]

function closestPrimes(left, right) {  const isPrime = new Array(right + 1).fill(true);  isPrime[0] = false;  isPrime[1] = false;  for (let i = 2; i * i <= right; i++) {    if (!isPrime[i]) continue;    for (let j = i * i; j <= right; j += i) isPrime[j] = false;  }  let prev = -1;  let best = [-1, -1];  for (let k = left; k <= right; k++) {    if (!isPrime[k]) continue;    if (prev !== -1 && (best[0] === -1 || k - prev < best[1] - best[0])) best = [prev, k];    prev = k;  }  return best;}console.log(closestPrimes(10, 19)); // [ 11, 13 ]console.log(closestPrimes(4, 6));   // [ -1, -1 ]

Make it stick

What's next

Several ideas in this lesson have a natural recursive form. gcd(a, b) = gcd(b, a % b) is a rule defined using itself, and so is xⁿ = (x^n/2)². Lesson 14 introduces recursion, which means a function that calls itself. It also explains the call stack, the list of active function calls that makes recursion work.