GCD and LCM
Greatest Common Divisor (GCD): the largest number that divides both a and b. Euclidean algorithm: gcd(a, b) = gcd(b, a % b). Base case: gcd(a, 0) = a. Time: O(log(min(a,b))) — each step reduces the smaller number by at least half. LCM: lcm(a, b) = a * b // gcd(a, b). To avoid overflow: compute a // gcd(a, b) * b instead of a * b // gcd(a, b). GCD of an array: gcd(arr) = gcd(gcd(arr[0], arr[1]), arr[2], …). Iteratively apply gcd(result, arr[i]). Use GCD for: simplifying fractions, finding the smallest repeating unit, the “minimum operations” class of problems where the answer is the range / gcd(all elements).
Prime Numbers
Check if n is prime: trial division up to sqrt(n). For each i from 2 to sqrt(n): if n % i == 0: not prime. O(sqrt(n)). Sieve of Eratosthenes: find all primes up to n. Create a boolean array is_prime[0..n], initialized True. Mark 0 and 1 as False. For each i from 2 to sqrt(n): if is_prime[i]: mark all multiples of i starting from i*i as False. Time: O(n log log n). Space: O(n). Prime factorization: for each i from 2 to sqrt(n): while n % i == 0: add i to factors, n //= i. If n > 1 after the loop: n is a prime factor. O(sqrt(n)).
Modular Arithmetic
Modular arithmetic prevents integer overflow in combinatorics problems. Key properties: (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. For division: modular inverse. a^(-1) mod m = a^(m-2) mod m (Fermat’s Little Theorem, when m is prime). Apply this when the answer must be returned “modulo 10^9+7” (standard in competitive programming and some interviews). Combination C(n, k) mod p: C(n,k) = factorial[n] * inverse(factorial[k]) * inverse(factorial[n-k]) % p. Precompute factorials and their modular inverses up to n.
Fast Power (Binary Exponentiation)
Compute a^n mod m in O(log n) instead of O(n). Key insight: a^n = (a^(n/2))^2 if n is even; a^(n/2))^2 * a if n is odd. Recursive: if n==0: return 1. half = power(a, n//2, m). if n%2==0: return half*half%m. else: return half*half*a%m. Iterative (preferred to avoid recursion overhead): result=1; a=a%m; while n>0: if n%2==1: result=result*a%m; a=a*a%m; n//=2. Applications: modular inverse (a^(p-2) mod p), RSA encryption, matrix exponentiation for Fibonacci in O(log n).
Bit-Based Math
Check power of 2: n & (n-1) == 0 (and n > 0). Powers of 2 have exactly one set bit. Count set bits: bin(n).count(‘1’) or use Brian Kernighan’s algorithm. Integer square root: binary search on [1, n], find largest k where k*k <= n. Avoid sqrt() due to floating-point precision. Reverse bits: for _ in range(32): result = (result <>= 1. Majority element: Boyer-Moore voting — candidate and count. For each element: if count==0: new candidate; elif element==candidate: count++; else: count–. The majority element (appears > n/2 times) survives.
Interview Tips
- “Return the answer modulo 10^9+7” means apply % (10**9+7) after every multiplication and addition to prevent overflow. Do not wait until the final answer — intermediate values overflow Python’s arbitrary precision but not C++/Java.
- Sieve of Eratosthenes is the go-to for “find all primes up to N” — much faster than checking each number individually.
- GCD shows up in unexpected places: “minimum number of operations to make all elements equal” often reduces to gcd of the differences.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide