SpaceComplexity

Coding Interview Math Cheat Sheet: Every Formula, One Place

June 6, 202610 min read
dsaalgorithmsinterview-prepleetcode
Coding Interview Math Cheat Sheet: Every Formula, One Place
TL;DR
  • 2^10 ≈ 10³ is the anchor that lets you estimate any log₂ in your head — binary search on 10⁹ items takes ≈30 steps.
  • Triangular sum n(n+1)/2 drives every nested-loop O(n²) derivation and pair-counting problem.
  • Modular subtraction requires a +m before the final mod; Java, C++, and Go return negative values without it.
  • Power-of-2 check n > 0 && (n & (n-1)) == 0 works because subtracting 1 flips all lower bits, giving AND = 0.
  • Integer overflow hits silently at 2^31-1 ≈ 2.1×10⁹; always use low + (high - low) / 2 for binary search midpoints.
  • GCD Euclidean algorithm runs in O(log min(a,b)); compute LCM as a/gcd(a,b)*b to avoid intermediate overflow.
  • XOR identities a^a=0 and a^0=a underlie the single-number trick and most bitmask enumeration patterns.

You don't need a math degree. But you do need to know that sum(1..n) = n*(n+1)/2, that log₂(10⁹) ≈ 30, and that n & (n-1) == 0 checks for a power of two. None of this is hard. Most of it takes thirty minutes to learn. And showing up without it costs you problems you could have solved.

What actually happens: you're in the interview, the question involves a billion-node tree, and your brain (which has run binary search hundreds of times) produces nothing. You know what log means. You've done this. And yet your mouth is saying "uh, log... base two... so..." while the interviewer writes something in their notes.

This is the reference you skim the night before. Every formula that actually shows up, nothing that doesn't.

Powers of 2 Are the Foundation of Everything

Binary search, heaps, bit manipulation, memory sizing, tree heights. They all trace back to the same table.

PowerValueRough Size
2^82561 byte worth of values
2^101,024~10³ (your most useful approximation)
2^1665,536max unsigned 16-bit int
2^201,048,576~10⁶
2^301,073,741,824~10⁹
2^312,147,483,648signed 32-bit int max + 1
2^324,294,967,296~4 × 10⁹

The anchor: 2^10 ≈ 10³. That one fact lets you estimate any log₂ in your head. You don't need the rest of the table memorized if you can derive it from there. You do need to actually derive it, though. Out loud. While being watched.

log₂(10⁹) Is 30. Know This.

You'll be asked about binary search on 10 million items, or a balanced BST with a billion nodes. You need to answer "about 30 operations" without hesitation.

nlog₂(n)
10³≈ 10
10⁶≈ 20
10⁹≈ 30
10¹²≈ 40

The pattern: every three orders of magnitude adds roughly 10 to the logarithm. Why? Because 2^10 ≈ 10^3, so log₂(10^3k) ≈ 10k.

Your interviewer is not waiting for long division. These numbers need to be instant.

Combining Complexities Is Where People Get It Wrong

The mistakes here are quiet and confident. The rules:

  • Drop constants: O(3n) = O(n). The constant doesn't matter asymptotically.
  • Drop lower-order terms: O(n² + n) = O(n²). At large n, n² dominates.
  • Sequential steps add: a loop that's O(n) followed by another O(n) loop is O(n), not O(2n) and not O(n²).
  • Nested steps multiply: an O(n) loop inside an O(n) loop is O(n²).
  • Keep independent variables separate: if your algorithm is O(n) on one array and O(m) on another, the result is O(n + m), not O(n).

The last one bites people on graph problems. BFS is O(V + E), not O(V) or O(E). Both terms matter when you don't know which dominates. "O(n)" is not wrong enough to stop the interview, but it's imprecise enough for the interviewer to write "fuzzy on graph complexity" in their notes.

Sum Formulas That Actually Show Up

Triangular numbers. The sum of the first n positive integers:

1 + 2 + 3 + ... + n = n(n+1) / 2

You've seen this before. In high school, probably while drawing something in the margin. It didn't feel important then. It shows up every time you analyze a nested loop where the inner bound shrinks.

This appears everywhere. When you have a nested loop where the inner loop runs 1, 2, 3, ..., n times, the total iterations are n(n+1)/2 = O(n²). It's also how you count pairs: n items have C(n,2) = n(n-1)/2 pairs.

Geometric series. The sum of a + ar + ar² + ... + arⁿ:

sum = a(rⁿ⁺¹ - 1) / (r - 1)

The special case you actually need for binary recursion: 1 + 2 + 4 + ... + 2ⁿ = 2ⁿ⁺¹ - 1. That's why the total work in a balanced recursion tree where each level doubles is O(n), not O(n log n). The leaves do O(n) total work and all the other levels add up to at most O(n) more.

The converging series 1 + 1/2 + 1/4 + ... = 2. Useful for amortized analysis.

Meme: Interviewer asks for nth Fibonacci number. The solution uses Binet's closed-form formula with Math.sqrt(5) and Math.pow. The interviewer's face: deeply unimpressed.

The formula works. The interviewer wants dynamic programming. These are both true simultaneously.

Modular Arithmetic: That + m Is Not Optional

Combinatorics questions often ask you to "output the result mod 10⁹+7." The rules:

(a + b) % m = ((a % m) + (b % m)) % m
(a * b) % m = ((a % m) * (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + m) % m

That + m in the subtraction rule is not optional. In Python, -1 % m gives a positive result because Python's modulo always returns non-negative. In Java, C++, and Go, -1 % m gives -1. Skip the + m in those languages and your answer is wrong. The tests will catch it. Probably at 11pm, after you've convinced yourself you're done.

The modulus 10⁹+7 (= 1,000,000,007) shows up constantly because it's prime and fits comfortably in a 32-bit signed int when adding, and in a 64-bit int when multiplying before taking mod.

For fast exponentiation (a^b mod m), use binary exponentiation in O(log b). Don't write a loop. The loop is O(b). b might be 10¹⁸. That loop is not finishing before the interview ends.

Deeper dive: modular arithmetic for coding interviews.

Combinatorics: The Formulas and When to Use Them

Permutations (order matters, picking k items from n):

P(n, k) = n! / (n - k)!

Combinations (order doesn't matter, choosing k items from n):

C(n, k) = n! / (k! * (n - k)!)

Total subsets of n elements = 2ⁿ (including empty set).

Total permutations of n elements = n!.

The symmetry property C(n, k) = C(n, n-k) lets you compute C(100, 97) as C(100, 3). Always feels like cheating. Not cheating.

Pair count: C(n, 2) = n(n-1)/2. If you reach for O(n²) on a pairs problem, you're right. n(n-1)/2 is still O(n²).

Factorials grow fast. 13! = 6,227,020,800, which already overflows a 32-bit int. 21! overflows a 64-bit int. Your high school calculator handled these fine because it was using floating-point. It was lying to you. For interview problems you need either big integers or modular arithmetic.

GCD, LCM, and Primes: Three Tools You Actually Need

GCD via the Euclidean algorithm:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Time: O(log min(a, b)). The key relationship: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.

LCM from GCD:

lcm(a, b) = a * b / gcd(a, b)

Compute a / gcd(a, b) * b, not a * b / gcd(a, b). The order matters when a and b are large enough to overflow the intermediate product.

Prime checking: trial division to √n. If n has a factor larger than √n, it must have a corresponding one smaller than √n, so you stop there.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

For counting all primes up to n, the Sieve of Eratosthenes runs in O(n log log n), which is essentially O(n) in practice. The prime sieve guide has the full implementation.

The GCD algorithm guide covers the proof and edge cases.

Bit Math: The Tricks Worth Memorizing

XOR properties (roughly 20% of bit manipulation problems):

a ^ a = 0
a ^ 0 = a
a ^ b ^ a = b

The classic use: find the single number in an array where every other element appears twice. XOR the whole array. Pairs cancel. The singleton survives. This works. Explaining why out loud sounds genuinely sharp.

Power of 2 check:

n > 0 and (n & (n - 1)) == 0

A power of 2 in binary is one 1-bit followed by zeros (8 = 1000). Subtracting 1 flips that bit and everything below it (7 = 0111). AND-ing gives zero. This looks like a typo. It is not.

Clear the lowest set bit:

x & (x - 1)

Iterate until x hits 0 and you've counted the set bits. Brian Kernighan's algorithm. Runs in O(number of set bits), not O(32).

Isolate the lowest set bit:

x & (-x)

In two's complement, -x is ~x + 1. AND-ing x with its negation extracts the lowest set bit. This is how Fenwick trees update and query efficiently.

Shift arithmetic: left shift by k = multiply by 2^k. Right shift by k (positive numbers) = floor divide by 2^k.

For bitmask-based subset enumeration and DP, see the full bitmask guide.

Integer Overflow: The Bug That Almost Works

int (32-bit signed):  max = 2³¹ - 1 = 2,147,483,647  (~2.1 × 10⁹)
long (64-bit signed): max = 2⁶³ - 1 ≈ 9.2 × 10¹⁸

When to worry: any time you multiply two values that might each approach 10⁵ or larger, the product might overflow a 32-bit int.

The canonical example is midpoint calculation in binary search. (low + high) / 2 overflows when low + high > 2³¹ - 1. The fix is low + (high - low) / 2. Joshua Bloch, one of Java's lead architects, found this exact bug in the Java standard library in 2006. The code had been there since 1997. Nine years. In the standard library. Written and reviewed by people who are very good at this.

Use low + (high - low) / 2 for midpoints.

The triangular sum n(n+1)/2 overflows a 32-bit int when n > ~65,000.

In Python, integers are arbitrary precision and never overflow. In Java, C++, Go, and Kotlin, they silently wrap around.

Military officers covered in medals: "WHEN DEVELOPERS QA TEST THEIR OWN CODE"

The overflow bug passes every test you write because you write tests where the inputs are small. The interviewer's test case has two numbers near INT_MAX.

That silent wraparound is one of the most common bugs in interview code that "almost works." It passes small cases. It fails the edge case the interviewer is about to try. Catch it yourself, before being told.

Before You Walk In

  • Powers of 2: Memorize 2^10 ≈ 10³. Derive everything else from there.
  • Log estimates: log₂(10⁶) ≈ 20, log₂(10⁹) ≈ 30. No hesitation.
  • Big-O rules: Sequential steps add, nested steps multiply, keep independent variables separate.
  • Sum formula: 1+2+...+n = n(n+1)/2. Nested loop analysis and pair counting.
  • Modular subtraction: Always add m before taking mod to avoid negatives in Java/C++/Go.
  • Modulus 10⁹+7: Prime, fits in 64-bit after one multiplication.
  • GCD: Euclidean algorithm, O(log min(a,b)). LCM = a/gcd(a,b)*b in that order.
  • Primes: Trial division to √n. Sieve for counting all primes up to n.
  • XOR: a^a=0, a^0=a. Pairs cancel. Singles survive.
  • Power of 2: n>0 and (n&(n-1))==0.
  • Overflow: int max ≈ 2.1×10⁹. Use low+(high-low)/2 for midpoints.

If you want to practice applying these under real pressure, SpaceComplexity runs voice-based mock interviews where the interviewer probes your reasoning in real time, the same way a Google or Meta interviewer would.

Further Reading