Number Theory Coding Problems: 48 Questions with Solutions
48 number theory coding problems — 14 easy · 19 medium · 15 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 48
- By difficulty: 14 easy · 19 medium · 15 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
Number theory problems are coding questions about integers themselves — 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
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
14 of the 48 Number Theory problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 34 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.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Check if Number is a Sum of Powers of Three Medium
- Smallest Value After Replacing With Sum of Prime Factors Medium
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
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Nth Magical Number Hard
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 8
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
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 / gcdand overflowing wherea / gcd * bwould 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
Easy (14)
- Check if Any Element Has Prime Frequency Array, Hash Table, Math
- Number of Beautiful Pairs Array, Hash Table, Math
- Prime In Diagonal Array, Math, Matrix
- Construct the Rectangle Math
- Sum of Squares of Special Elements Array, Math
- Count Distinct Numbers on Board Math, Simulation
- Sum Multiples Math
- Number of Common Factors Math, Enumeration
- Smallest Even Multiple Math
- Three Divisors Math
- X of a Kind in a Deck of Cards Array, Math
- Find Greatest Common Divisor of Array Array, Math
- Prime Factorisation Math
- Add Digits Math, Simulation
Medium (19)
- Insert Greatest Common Divisors in Linked List Linked List, Math
- Digit Operations to Make Two Integers Equal Math, Graph, Heap (Priority Queue)
- Prime Pairs With Target Sum Array, Math, Enumeration
- Minimize the Maximum of Two Arrays Math, Binary Search
- Closest Prime Numbers in Range Math
- Distinct Prime Factors of Product of Array Array, Hash Table, Math
- Simplified Fractions Math, String
- Four Divisors Array, Math
- Ugly Number III Math, Binary Search, Combinatorics
- Smallest Integer Divisible by K Hash Table, Math
- Prime Palindrome Math
- Mirror Reflection Math, Geometry
- Number of Subarrays With LCM Equal to K Array, Math
- Number of Subarrays With GCD Equal to K Array, Math
- The kth Factor of n Math
- Closest Divisors Math
- Prime Subtraction Operation Array, Math, Greedy
- Smallest Value After Replacing With Sum of Prime Factors Math, Simulation
- Check if Number is a Sum of Powers of Three Math
Hard (15)
- GCD Sort of an Array Array, Math, Union Find
- Count Valid Paths in a Tree Math, Dynamic Programming, Tree
- Find the Number of Subsequences With Equal GCD Array, Math, Dynamic Programming
- Minimum Deletions to Make Array Divisible Array, Math, Sorting
- Replace Non-Coprime Numbers in Array Array, Math, Stack
- Maximize Score After N Operations Math, Dynamic Programming, Bitmask
- Check if Point Is Reachable Math
- Reaching Points Math
- Count Ways to Make Array With Product Array, Math, Dynamic Programming
- Count the Number of Ideal Arrays Math, Dynamic Programming, Combinatorics
- Apply Operations to Maximize Score Array, Math, Stack
- Largest Component Size by Common Factor Array, Math, Union Find
- Smallest Good Base Math, Binary Search
- Preimage Size of Factorial Zeroes Function Math, Binary Search
- Nth Magical Number Math, Binary Search
Companies that ask number theory problems
- Amazon 42 problems on number theory
- Google 30 problems on number theory
- TCS 11 problems on number theory
- Infosys 7 problems on number theory
- Adobe 6 problems on number theory
- Microsoft 5 problems on number theory
- Meta 3 problems on number theory
- Accenture 2 problems on number theory
- Apple 2 problems on number theory
- Capgemini 2 problems on number theory
- Wipro 2 problems on number theory
- Capital One 1 problem on number theory
Common questions
What is number theory in coding problems?
The part of programming problems about integers themselves: primes, divisibility, GCD and LCM, modular arithmetic and the digits of a number. It appears as "count the divisors", "is it prime", "return the answer modulo 10^9 + 7" or "reduce the fraction".
Which number theory algorithms should I know?
The sieve of Eratosthenes for every prime up to n in O(n log log n), Euclid's algorithm for GCD in O(log n), fast modular exponentiation in O(log n), trial division up to √n to factorise, and Fermat's little theorem for a modular inverse when the modulus is prime.
Why is the answer asked modulo 10^9 + 7?
Because the true answer overflows a 64-bit integer. 10^9 + 7 is prime and small enough that the product of two remainders still fits in 64 bits, so you can reduce after every addition and multiplication without changing the final result.
How do I avoid overflow in number theory problems?
Multiply in 64-bit integers (long long in C++, long in Java) and reduce modulo after every step. Compute an LCM as a / gcd(a, b) * b rather than a * b / gcd(a, b), and in JavaScript use BigInt once values pass 2^53.
Next topic: Sieve of Eratosthenes