Number Theory Coding Problems: 25 Questions with Solutions

25 number theory coding problems — 13 easy · 5 medium · 7 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.

Problems: 25
By difficulty: 13 easy · 5 medium · 7 hard
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Cost: Free on every plan; sign in to run and submit

Primes, divisors, greatest common divisors and modular arithmetic. Sieving primes, reducing fractions, computing powers modulo a number and reasoning about remainders are the moves; these problems practise them along with the integer limits that make a naive product overflow.

How number theory works, step by step

Greatest common divisor, with Euclid's algorithm. Example: a = 252, b = 105

Euclid's rule is gcd(a, b) = gcd(b, a mod b): a number that divides both a and b also divides a − q × b. Picture 252 and 105 as the sides of a rectangle: their gcd is the side of the largest square that tiles it exactly.
Cut a 105 × 105 square off the 252 × 105 rectangle, leaving 147 × 105. Any number that divides 252 and 105 also divides 252 − 105 = 147, so the gcd has not changed.
Square 2 leaves 42 × 105, and 42 < 105, so no more fit: 252 = 2 × 105 + 42. A single mod does both subtractions at once, and the problem becomes gcd(105, 42).
The short side is now 42, so cut 42 × 42 squares from the 42 × 105 strip: the first leaves 42 × 63. Same rule, smaller numbers: gcd(105, 42) = gcd(63, 42).
Square 2 leaves 42 × 21, and 21 < 42, so no more fit: 105 = 2 × 42 + 21. A single mod does both subtractions at once, and the problem becomes gcd(42, 21).
The short side is now 21, so cut 21 × 21 squares from the 42 × 21 strip: the first leaves 21 × 21. Same rule, smaller numbers: gcd(42, 21) = gcd(21, 21).
Square 2 uses up the strip exactly: 42 = 2 × 21 + 0. The remainder is 0, so gcd(42, 21) = gcd(21, 0) = 21 and the algorithm stops.
The 21 × 21 square tiles the whole 252 × 105 rectangle: 252 = 12 × 21 and 105 = 5 × 21, and no bigger square does. gcd(252, 105) = 21 after 3 divisions; the remainder at least halves every two steps, so Euclid is O(log min(a, b)).

Number Theory study plan

12 of the 25 Number Theory problems (4 easy, 5 medium and 3 hard) over 7 days, about 7 h in all — the pattern first, then easiest to hardest. After that, the other 13 in the full list below are practice at your own pace. Then move on to Sieve of Eratosthenes.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Find Greatest Common Divisor of Array Easy
Prime Factorisation Easy
Add Digits Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

X of a Kind in a Deck of Cards Easy
The kth Factor of n Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Prime Subtraction Operation Medium
Closest Divisors Medium

Day 5

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Nth Magical Number Hard

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Preimage Size of Factorial Zeroes Function Hard

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Smallest Good Base Hard

Next topic: Sieve of Eratosthenes

Number Theory: the essentials

When to reach for it

Statements about divisors, multiples, primes, coprime pairs or least common multiples, and any answer requested "modulo 10⁹ + 7". Also sequences that repeat with a period, such as the k-th number divisible by a or b, or an answer that depends only on n modulo something.

The pattern

Euclid's algorithm gives gcd(a, b) = gcd(b, a % b), and lcm(a, b) = a / gcd(a, b) × b — dividing first keeps the intermediate value small. Divisors come in pairs (d, n / d), so trial division only has to reach √n. To test many numbers for primality, sieve once up to the largest. Under a modulus, reduce after every addition and multiplication; division needs a modular inverse instead.

def sieve(n):                       # is_prime[i] for 0 <= i <= n, n >= 1
    is_prime = [False, False] + [True] * (n - 1)
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
        p += 1
    return is_prime

Cost

Euclid's algorithm is O(log min(a, b)); trial division is O(√n); the sieve is O(n log log n) time and O(n) space; fast modular exponentiation is O(log e) for exponent e.

Common mistakes

Computing a * b / gcd and overflowing where a / gcd * b would not.
Reducing modulo only at the end, after an intermediate product has already overflowed (in Python it is correct, just slow).
A negative remainder after subtraction in Java, C++ or JavaScript; write ((a - b) % m + m) % m.
Counting √n twice when listing the divisor pairs of a perfect square.

Start with

Find Greatest Common Divisor of Array: Euclid's algorithm.
Prime Factorisation: trial division up to √n.
The kth Factor of n: divisor pairs in order.

All number theory problems

Companies that ask number theory problems

Amazon 22 problems on number theory
Google 11 problems on number theory
TCS 9 problems on number theory
Infosys 7 problems on number theory
Adobe 6 problems on number theory
Microsoft 3 problems on number theory
Accenture 2 problems on number theory
Apple 2 problems on number theory
Capgemini 2 problems on number theory
Meta 2 problems on number theory
Wipro 2 problems on number theory
Cognizant 1 problem on number theory