Autocoder

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.

Problems10, easy to hard
LanguagesPython and Java
Toolboxgcd, 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.

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. 1

    Compute the gcd and lcm of two numbers.

    easy

    Euclid'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.

    python
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    
    def lcm(a, b):
        return a // gcd(a, b) * b
    java
    import 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. 2

    Check whether a number is prime.

    easy

    A 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.

    python
    def is_prime(n):
        if n < 2:
            return False
        i = 2
        while i * i <= n:
            if n % i == 0:
                return False
            i += 1
        return True
    java
    import 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. 3

    Count the primes strictly less than n (sieve of Eratosthenes).

    medium

    Keep 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.

    python
    def 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)
    java
    import 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. 4

    Prime factorisation of a number.

    medium

    Divide 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.

    python
    def 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 res
    java
    import 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. 5

    Count the trailing zeroes of n factorial.

    easy

    Each 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).

    python
    def trailing_zeroes(n):
        count = 0
        while n:
            n //= 5
            count += n
        return count
    java
    import java.util.*;
    
    class Solution {
        static int trailingZeroes(int n) {
            int count = 0;
            while (n > 0) {
                n /= 5;
                count += n;
            }
            return count;
        }
    }
  6. 6

    Happy number: repeatedly replace n by the sum of the squares of its digits; does it reach 1?

    easy

    Either 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.

    python
    def 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 == 1
    java
    import 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. 7

    Reverse the digits of a 32-bit signed integer, returning 0 if the result overflows.

    medium

    Pop 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.

    python
    def 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 0
    java
    import 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. 8

    Excel sheet column title: convert 1, 2, ..., 26, 27, 28 into A, B, ..., Z, AA, AB.

    medium

    It 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).

    python
    def convert_to_title(n):
        res = []
        while n:
            n -= 1
            res.append(chr(65 + n % 26))
            n //= 26
        return "".join(reversed(res))
    java
    import 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. 9

    Modular exponentiation: compute a^b mod m for a large exponent.

    medium

    Use 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.

    python
    def 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 % m
    java
    import 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. 10

    Compute nCr modulo a prime p, such as 1,000,000,007.

    hard

    Direct 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).

    python
    def 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) % p
    java
    import 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

See all in this section