Math for DSA

You do not need a mathematics degree to excel at DSA interviews — but a handful of mathematical ideas appear in problems so frequently that not knowing them creates avoidable stumbling blocks. This page covers the essential math toolkit every competitive programmer and interview candidate needs.

Integer Overflow

JavaScript uses 64-bit floating-point (IEEE 754) for all numbers, which gives exact integer arithmetic only up to Number.MAX_SAFE_INTEGER = 2^53 - 1 = 9,007,199,254,740,991. Beyond that, bit-level precision is lost and results silently become wrong.

// Safe range check
console.log(Number.MAX_SAFE_INTEGER);  // 9007199254740991
console.log(Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2); // true ← BUG

// Use BigInt for exact arithmetic beyond safe range
const a = BigInt("999999999999999999");
const b = BigInt("999999999999999999");
console.log(a * b);  // 999999999999999998000000000000000001n  (exact)

// Classic overflow trap: LeetCode "Two Sum" with index product
// Use modulo to keep results in range when the answer is defined mod M
const MOD = 1_000_000_007n;
function modMul(a: bigint, b: bigint): bigint {
  return (a * b) % MOD;
}

Note

In most competitive programming problems that involve large products or sums, the problem will tell you to "return the answer modulo 10^9 + 7." This is your signal to apply modular arithmetic throughout all multiplications and additions.

Floor, Ceil, and Rounding

// Integer division in JavaScript
Math.floor(7 / 2)   // 3  — rounds toward -Infinity
Math.ceil(7 / 2)    // 4  — rounds toward +Infinity
Math.round(7 / 2)   // 4  — rounds to nearest (half rounds up)

// Bitwise floor for positive integers (much faster)
(7 / 2) | 0         // 3  — same as Math.floor for positive numbers

// Mid-point in binary search (prevents overflow in languages with fixed integers)
const lo = 0, hi = 1_000_000_000;
const mid = lo + Math.floor((hi - lo) / 2);  // safe
// const mid = Math.floor((lo + hi) / 2);    // could overflow in C++/Java

// Number of digits in n
function digitCount(n: number): number {
  return Math.floor(Math.log10(n)) + 1;
}
console.log(digitCount(12345)); // 5

Fast Exponentiation — O(log n)

Computing base^exp naively loops exp times: O(exp). Fast exponentiation (binary exponentiation) halves the exponent at each step, giving O(log exp). This is essential for modular exponentiation used in cryptography and competitive programming.

// Iterative fast power   O(log exp)
function fastPow(base: number, exp: number): number {
  let result = 1;
  while (exp > 0) {
    if (exp & 1) {        // if current bit of exp is 1
      result *= base;
    }
    base *= base;         // square the base
    exp >>= 1;            // move to next bit
  }
  return result;
}

// Modular fast power (prevents overflow)
function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
  let result = 1n;
  base = base % mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}

console.log(fastPow(2, 10));            // 1024
console.log(modPow(2n, 100n, 1000000007n)); // 976371285n

Logarithm Base Conversion

JavaScript only provides Math.log (natural log) and Math.log2 / Math.log10. The change-of-base formula lets you compute any logarithm: log_b(x) = log(x) / log(b).

function logBase(x: number, base: number): number {
  return Math.log(x) / Math.log(base);
}

// How many times can you halve n before reaching 1?  → log2(n)
console.log(Math.log2(1024));        // 10  (binary search depth)
console.log(logBase(1000, 10));      // 3   (digits in 1000)
console.log(Math.ceil(logBase(n => Math.log2(n + 1))); // bits needed to store n

Series Summation Formulas

Series	Formula	Example
Arithmetic (1+2+…+n)	n(n+1)/2	1+2+3+4+5 = 15
Sum of squares	n(n+1)(2n+1)/6	1+4+9+16+25 = 55
Geometric (1+r+r²+…+r^n)	(r^(n+1) - 1) / (r - 1)	1+2+4+8 = 15
Infinite geometric \|r\|<1	1 / (1 - r)	1 + 0.5 + 0.25 + … = 2

// Arithmetic sum: appears in "Two Sum" analysis, prefix sums, etc.
function arithmeticSum(n: number): number {
  return (n * (n + 1)) / 2;
}

// Geometric sum: total nodes in complete binary tree of height h
// Each level has 2^0, 2^1, ..., 2^h nodes → sum = 2^(h+1) - 1
function completeBinaryTreeNodes(height: number): number {
  return (1 << (height + 1)) - 1;  // 2^(h+1) - 1
}

console.log(arithmeticSum(100));          // 5050
console.log(completeBinaryTreeNodes(3)); // 15  (1+2+4+8)

The Pigeonhole Principle

If n+1 items are placed into n containers, at least one container must hold two or more items. Simple idea — but it proves the existence of duplicates and drives several algorithmic insights.

Any array of n+1 integers in range [1..n] must contain at least one duplicate
If you hash n distinct keys into m < n buckets, a collision must exist
In the "Find the Duplicate Number" problem (LC 287), a duplicate must exist by pigeonhole
Birthday paradox: only ~23 people needed for a 50% collision probability in 365 buckets

// LeetCode 287 — Find the Duplicate Number
// Array of n+1 integers where each integer is in [1, n]
// By pigeonhole, at least one integer appears more than once.
// Floyd's cycle detection solves it in O(n) time, O(1) space:
function findDuplicate(nums: number[]): number {
  let slow = nums[0];
  let fast = nums[0];
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

console.log(findDuplicate([1, 3, 4, 2, 2])); // 2

Two's Complement

Negative integers are stored in two's complement: flip all bits of the positive form and add 1. This makes subtraction hardware-free (a - b = a + (~b + 1)) and explains several bit tricks.

//  5  in binary:  0101
// -5  step 1 flip:  1010
// -5  step 2 +1:    1011

// Key consequences:
// ~n === -(n+1)      e.g. ~5 === -6
// -n === ~n + 1
// n & (-n) isolates the lowest set bit (LSB)

//  12 = 1100
// -12 = 0100  (two's complement)
// 12 & -12 = 0100  → isolates bit 2 (value 4)
console.log(12 & -12); // 4

// Used in Fenwick tree (BIT) index arithmetic
function nextIndex(i: number): number {
  return i + (i & -i);  // add LSB to move to parent
}
function parentIndex(i: number): number {
  return i - (i & -i);  // subtract LSB to move toward root
}

Absolute Value Without Branching

// Branchless absolute value using arithmetic right shift
// Arithmetic right shift of -1 gives all-1s mask: 0xFFFFFFFF
// Arithmetic right shift of 0 gives all-0s mask: 0x00000000
function absNoBranch(n: number): number {
  const mask = n >> 31;          // -1 if negative, 0 if positive
  return (n ^ mask) - mask;      // flip bits if negative, add 1
}

console.log(absNoBranch(-7));  // 7
console.log(absNoBranch(7));   // 7

Tip

These formulas are not just academic — they appear in solutions to real LeetCode problems. Arithmetic sum shows up in "Missing Number," fast exponentiation in "Pow(x,n)," and pigeonhole reasoning in "Find the Duplicate Number." Recognising the math pattern is often the hardest step.