Math and number theory interview questions with solutions
Last updated 2026-11-19
Math questions in coding rounds are mostly about a small toolbox: divisibility and gcd, primes and the sieve, digit manipulation, modular arithmetic and careful handling of overflow. The skill is to replace an obvious brute-force loop with a mathematical fact that shrinks the work, such as testing divisors only up to the square root.
The ten problems below move from basic number properties to modular exponentiation and combinations modulo a prime, which appear in counting problems. For bit-level arithmetic see bit manipulation questions, and for exponentiation by squaring in recursive form see recursion questions. Test-day advice is in the DSA coding round guide.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Toolbox | gcd, sieve, modular arithmetic, Fermat inverse |
Facts to keep ready
gcd(a, b) = gcd(b, a mod b), and lcm(a, b) = a / gcd(a, b) * b (divide first to avoid overflow). A composite number n has a divisor at most sqrt(n). The sieve of Eratosthenes marks multiples of each prime starting from its square. Modular arithmetic is compatible with addition and multiplication: (a * b) mod m = ((a mod m) * (b mod m)) mod m.
For a prime modulus p, the inverse of x is x^(p - 2) mod p (Fermat's little theorem), which turns division into multiplication. Python integers are unbounded; in Java use long and reduce after every multiplication so intermediate values stay below 2^63.
- Divisors and primes: loop to the square root only.
- Many primes: sieve in O(n log log n).
- Powers modulo m: square and multiply in O(log n).
- Counting modulo 10^9 + 7: factorials plus modular inverses.
Overflow and limits
The most common failure is silent overflow: a 32-bit multiplication of two numbers near a billion exceeds the range. Use 64-bit arithmetic, reduce early, or check the range before multiplying. Also be explicit about negative inputs and zero.
Math and number theory interview questions with solutions: questions with worked answers
1 Compute the gcd and lcm of two numbers.
easyEuclid's algorithm replaces (a, b) with (b, a mod b) until b is zero; the remaining a is the gcd. The lcm is a divided by gcd, times b. Dividing before multiplying keeps the intermediate value smaller. The number of steps is logarithmic. Time O(log min(a, b)), space O(1).. Edge cases: one value is 0 (gcd is the other), equal values, large values near the type limit when computing the lcm.
pythondef gcd(a, b): while b: a, b = b, a % b return a def lcm(a, b): return a // gcd(a, b) * bjavaimport java.util.*; class Solution { static long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; } static long lcm(long a, long b) { return a / gcd(a, b) * b; } }2 Check whether a number is prime.
easyA composite number has a divisor no larger than its square root, so test divisors from 2 while i * i <= n. Numbers below 2 are not prime. You can halve the work by handling 2 separately and testing odd divisors only. Time O(sqrt(n)), space O(1).. Edge cases: 0, 1 and negatives (not prime), 2 (the only even prime), perfect squares of primes such as 49.
pythondef is_prime(n): if n < 2: return False i = 2 while i * i <= n: if n % i == 0: return False i += 1 return Truejavaimport java.util.*; class Solution { static boolean isPrime(int n) { if (n < 2) return false; for (long i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } }3 Count the primes strictly less than n (sieve of Eratosthenes).
mediumKeep a boolean array marked prime. For each prime i with i * i < n, mark its multiples from i * i upwards as composite; smaller multiples were already marked by smaller primes. The count of true entries at the end is the answer. Time O(n log log n), space O(n).. Edge cases: n below 3 (0 primes), n = 3 (one prime, 2), large n needing memory care.
pythondef count_primes(n): if n < 3: return 0 s = [True] * n s[0] = s[1] = False i = 2 while i * i < n: if s[i]: for j in range(i * i, n, i): s[j] = False i += 1 return sum(s)javaimport java.util.*; class Solution { static int countPrimes(int n) { if (n < 3) return 0; boolean[] composite = new boolean[n]; int count = 0; for (int i = 2; i < n; i++) { if (composite[i]) continue; count++; for (long j = (long) i * i; j < n; j += i) composite[(int) j] = true; } return count; } }4 Prime factorisation of a number.
mediumDivide out each factor from 2 upwards while the factor squared is at most the remaining number, counting its exponent. If a number greater than 1 remains, it is itself a prime factor. For 360 the result is 2^3 * 3^2 * 5. Time O(sqrt(n)), space O(number of distinct primes).. Edge cases: n = 1 (no factors), n prime, n a prime power, large prime remainder.
pythondef prime_factors(n): res = {} p = 2 while p * p <= n: while n % p == 0: res[p] = res.get(p, 0) + 1 n //= p p += 1 if n > 1: res[n] = res.get(n, 0) + 1 return resjavaimport java.util.*; class Solution { static Map<Long, Integer> primeFactors(long n) { Map<Long, Integer> res = new TreeMap<>(); for (long p = 2; p * p <= n; p++) { while (n % p == 0) { res.merge(p, 1, Integer::sum); n /= p; } } if (n > 1) res.merge(n, 1, Integer::sum); return res; } }5 Count the trailing zeroes of n factorial.
easyEach trailing zero comes from a factor of 10 = 2 * 5, and factors of 2 are plentiful, so count the factors of 5 in 1..n. That is n/5 + n/25 + n/125 + ..., because multiples of 25 contribute two fives, and so on. The loop divides n by 5 repeatedly. Time O(log5 n), space O(1).. Edge cases: n below 5 (0), n = 25 (6), very large n (do not compute the factorial).
pythondef trailing_zeroes(n): count = 0 while n: n //= 5 count += n return countjavaimport java.util.*; class Solution { static int trailingZeroes(int n) { int count = 0; while (n > 0) { n /= 5; count += n; } return count; } }6 Happy number: repeatedly replace n by the sum of the squares of its digits; does it reach 1?
easyEither the process reaches 1 or it enters a cycle that never contains 1. Detect the cycle with a set of seen values (or Floyd's tortoise and hare for O(1) space). If 1 is reached, the number is happy. For 19: 82, 68, 100, 1. Time O(log n) per step with a bounded number of steps, space O(number of seen values).. Edge cases: n = 1 (happy), a number entering the 4, 16, 37, 58, 89, 145, 42, 20 cycle, large n.
pythondef is_happy(n): seen = set() while n != 1 and n not in seen: seen.add(n) n = sum(int(d) ** 2 for d in str(n)) return n == 1javaimport java.util.*; class Solution { static boolean isHappy(int n) { Set<Integer> seen = new HashSet<>(); while (n != 1 && seen.add(n)) { int s = 0; while (n > 0) { int d = n % 10; s += d * d; n /= 10; } n = s; } return n == 1; } }7 Reverse the digits of a 32-bit signed integer, returning 0 if the result overflows.
mediumPop digits with % 10 and push them with r = r * 10 + d. In Java, check for overflow before multiplying: if r is already beyond MAX / 10 (or equal with a last digit above 7), or below MIN / 10 (or equal with a last digit below -8), return 0. In Python, reverse then compare with the 32-bit range. Time O(number of digits), space O(1).. Edge cases: trailing zeroes (120 becomes 21), negative numbers, results beyond 2^31 - 1.
pythondef reverse_int(x): sign = -1 if x < 0 else 1 r = int(str(abs(x))[::-1]) * sign return r if -2**31 <= r <= 2**31 - 1 else 0javaimport java.util.*; class Solution { static int reverse(int x) { int r = 0; while (x != 0) { int d = x % 10; x /= 10; if (r > Integer.MAX_VALUE / 10 || (r == Integer.MAX_VALUE / 10 && d > 7)) return 0; if (r < Integer.MIN_VALUE / 10 || (r == Integer.MIN_VALUE / 10 && d < -8)) return 0; r = r * 10 + d; } return r; } }8 Excel sheet column title: convert 1, 2, ..., 26, 27, 28 into A, B, ..., Z, AA, AB.
mediumIt is base 26 with no zero digit, so subtract one before each division. Repeatedly do n -= 1, take n % 26 as the next letter (from the right) and divide n by 26. The subtraction shifts the range from 1..26 to 0..25. For 28 you get AB. Time O(log26 n), space O(log26 n).. Edge cases: n = 26 (Z, not A0), n = 27 (AA), n = 52 (AZ), n = 702 (ZZ).
pythondef convert_to_title(n): res = [] while n: n -= 1 res.append(chr(65 + n % 26)) n //= 26 return "".join(reversed(res))javaimport java.util.*; class Solution { static String convertToTitle(int n) { StringBuilder sb = new StringBuilder(); while (n > 0) { n--; sb.append((char) ('A' + n % 26)); n /= 26; } return sb.reverse().toString(); } }9 Modular exponentiation: compute a^b mod m for a large exponent.
mediumUse square and multiply. Look at the exponent in binary: when the lowest bit is 1, multiply the result by the current base (mod m); then square the base (mod m) and shift the exponent right. This takes O(log b) multiplications instead of b. Python has pow(a, b, m) built in, and Java should use long and reduce after each multiplication. Time O(log b), space O(1).. Edge cases: b = 0 (result 1 mod m), m = 1 (result 0), a larger than m, overflow in Java if m exceeds about 3 * 10^9.
pythondef mod_pow(a, b, m): result = 1 a %= m while b > 0: if b & 1: result = result * a % m a = a * a % m b >>= 1 return result % mjavaimport java.util.*; class Solution { static long modPow(long a, long b, long m) { long result = 1; a %= m; while (b > 0) { if ((b & 1) == 1) result = result * a % m; a = a * a % m; b >>= 1; } return result % m; } }10 Compute nCr modulo a prime p, such as 1,000,000,007.
hardDirect factorial division fails because the numbers are huge and division does not work modulo p. Precompute factorials mod p, then nCr = n! * inverse(r!) * inverse((n - r)!) mod p, with each inverse computed by Fermat's little theorem as x^(p - 2) mod p. This needs p prime and n < p. Time O(n) to build factorials, then O(log p) per query; space O(n).. Edge cases: r greater than n (0), r = 0 or r = n (1), n at or above p (the formula breaks).
pythondef ncr_mod(n, r, p=10**9 + 7): if r < 0 or r > n: return 0 fact = [1] * (n + 1) for i in range(1, n + 1): fact[i] = fact[i - 1] * i % p return fact[n] * pow(fact[r] * fact[n - r] % p, p - 2, p) % pjavaimport java.util.*; class Solution { static final long P = 1_000_000_007L; static long modPow(long a, long b, long m) { long result = 1; a %= m; while (b > 0) { if ((b & 1) == 1) result = result * a % m; a = a * a % m; b >>= 1; } return result; } static long ncrMod(int n, int r) { if (r < 0 || r > n) return 0; long[] fact = new long[n + 1]; fact[0] = 1; for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % P; return fact[n] * modPow(fact[r] * fact[n - r] % P, P - 2, P) % P; } }
Frequently asked questions
Why test divisors only up to the square root?
If n = a * b with a <= b, then a <= sqrt(n). So any composite number has a divisor in that range, and checking beyond it is wasted work.
How do I avoid overflow in lcm?
Divide before multiplying: a / gcd(a, b) * b. For very large inputs use a 64-bit type or BigInteger in Java; Python integers do not overflow.
When is the sieve better than checking each number?
When you need all primes up to n, or many primality queries. The sieve takes O(n log log n) in total, while trial division costs O(sqrt(n)) for each number.
Why is 10^9 + 7 used as a modulus?
It is a prime below 2^31, so products of two residues fit in a 64-bit integer and every non-zero residue has a modular inverse.
Which pages cover bit-level arithmetic?
See bit manipulation questions for XOR and shifts, and recursion questions for recursive fast power.
Related guides
More in DSA Interview Questions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions