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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How does the Euclidean algorithm compute GCD efficiently?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The Euclidean algorithm: gcd(a, b) = gcd(b, a mod b). Base case: gcd(a, 0) = a. Example: gcd(48, 18) = gcd(18, 48%18=12) = gcd(12, 18%12=6) = gcd(6, 12%6=0) = 6. Why it works: any divisor of both a and b also divides a mod b (since a mod b = a – floor(a/b)*b). Time complexity: O(log(min(a,b))) — each step reduces the larger number by at least half (Fibonacci numbers are the worst case). Python: math.gcd(a, b). Recursive: def gcd(a, b): return a if b==0 else gcd(b, a%b). LCM: lcm(a,b) = a // gcd(a,b) * b. Divide before multiply to prevent overflow: (a // gcd(a,b)) * b not a*b//gcd(a,b).”
}
},
{
“@type”: “Question”,
“name”: “How does the Sieve of Eratosthenes work?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The Sieve finds all primes up to n. Algorithm: create is_prime[0..n] = True. Set is_prime[0]=is_prime[1]=False. For i from 2 to sqrt(n): if is_prime[i]: mark i*i, i*i+i, i*i+2i, … as False (all multiples of i, starting from i^2 because smaller multiples were already marked by smaller primes). Why start at i^2: any multiple of i less than i^2 has a smaller prime factor that already marked it. Primes: all indices where is_prime[i] is still True. Time: O(n log log n) (sum of 1/p for primes p up to n). Space: O(n). For finding primes up to 10^7: the sieve runs in under 1 second and uses ~10MB. For 10^9: too much memory — use a segmented sieve or probabilistic primality test (Miller-Rabin).”
}
},
{
“@type”: “Question”,
“name”: “What is modular arithmetic and why is 10^9+7 commonly used?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Modular arithmetic computes with remainders. (a + b) mod m = ((a mod m) + (b mod m)) mod m. Same for multiplication: (a * b) mod m = ((a mod m) * (b mod m)) mod m. This keeps intermediate values small (under m) preventing integer overflow. 10^9+7 (= 1,000,000,007) is used because: it is prime (enables modular inverses via Fermat’s Little Theorem: a^(-1) mod p = a^(p-2) mod p). It fits in a 32-bit integer (2^31-1 = 2.1*10^9 > 10^9+7). The product of two values mod 10^9+7 fits in a 64-bit integer ((10^9+6)^2 < 10^18 0: if n%2==1: result=result*a%m; a=a*a%m; n//=2; return result. Example: 2^10 mod 1000 = ((2^5)^2) mod 1000 = (32^2) mod 1000 = 1024 mod 1000 = 24. Applications: modular inverse (a^(p-2) mod p by Fermat’s Little Theorem, requires p prime). RSA decryption. Fibonacci in O(log n) using matrix exponentiation: [[1,1],[1,0]]^n gives Fibonacci numbers.”
}
},
{
“@type”: “Question”,
“name”: “What is the Boyer-Moore voting algorithm for finding the majority element?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Majority element: appears more than n/2 times. Boyer-Moore voting: one pass, O(1) space. Maintain candidate and count. For each element: if count==0: candidate=element; count=1. elif element==candidate: count++. else: count–. After the pass, candidate is the majority element (if one exists). Why it works: the majority element appears > n/2 times. Every vote-cancellation (count–) cancels one majority vote with one non-majority vote. The majority has more votes than all non-majority elements combined, so it always survives. Verification: if the problem does not guarantee a majority exists, do a second pass to count occurrences of candidate and verify > n/2. Extension to n/3 majority (appears > n/3 times): maintain two candidates and two counts. At most 2 such elements can exist.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide