AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Number Theory coding problems

Number theory problems are coding questions about integers themselves — primes, divisors, greatest common divisors and modular arithmetic.

48 problems · 14 easy · 19 medium · 15 hard · judged by hidden tests in 13 languages

48problems

14 easy

19 medium

15 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Find Greatest Common Divisor of Array

How it works

Number Theory, step by step

Greatest common divisor, with Euclid's algorithm

a = 252, b = 105

252 × 105gcd(252, 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.

0:01 / 0:30Step 1 of 8
Transcript · 8 steps

Study plan

Learn number theory in 8 days

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.

  1. Day 1

    about 1 h 15 min

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

  2. Day 2

    about 55 min

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

  3. Day 3

    about 1 h 10 min

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

  4. Day 4

    about 1 h 10 min

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

  5. Day 5

    about 1 h 10 min

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

  6. Day 6

    about 50 min

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

  7. Day 7

    about 50 min

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

  8. Day 8

    about 50 min

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

    Next topic: Sieve of Eratosthenes

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

10510542422121252 = 2 × 105 + 42105 = 2 × 42 + 2142 = 2 × 21 + 0gcd(252, 105) = gcd(105, 42) = gcd(42, 21) = gcd(21, 0) = 21
Greatest common divisor, with Euclid's algorithm. Example: a = 252, b = 105
  1. 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.
  2. 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.
  3. 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).
  4. 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).
  5. 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).
  6. 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).
  7. 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.
  8. 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.

Day 4

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

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.

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.

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

All number theory problems

Easy (14)

Medium (19)

Hard (15)

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