🧮 Complete Number Theory Interview Guide

All Interview Questions from Basic to Expert Level

📋Table of Contents

🟢Basic Level Problems (1-15)

Foundation concepts - Usually asked to Junior developers or as warm-up questions

1. Check if Number is Prime
Easy
Given an integer n, determine if it is a prime number.
Input: n = 17
Input: n = 4
Output: true
Output: false
Constraints: 1 ≤ n ≤ 10^6
Hint: Check divisors only up to √n for optimization.
Time: O(√n) | Space: O(1)
Asked by: Google, Microsoft, Amazon, Apple
2. Count Primes
Medium
Count the number of prime numbers less than a non-negative integer n.
Input: n = 10
Input: n = 0
Output: 4 (2,3,5,7)
Output: 0
Constraints: 0 ≤ n ≤ 5 × 10^6
Hint: Use Sieve of Eratosthenes for efficient bulk prime generation.
Time: O(n log log n) | Space: O(n)
LeetCode #204
Asked by: Amazon, Microsoft, Adobe, Uber
3. Greatest Common Divisor (GCD)
Easy
Find the greatest common divisor of two integers a and b.
Input: a = 48, b = 18
Input: a = 17, b = 13
Output: 6
Output: 1
Constraints: 1 ≤ a, b ≤ 10^9
Hint: Use Euclidean algorithm: gcd(a,b) = gcd(b, a%b).
Time: O(log min(a,b)) | Space: O(1)
Asked by: Google, Facebook, Apple, Netflix
4. Least Common Multiple (LCM)
Easy
Find the least common multiple of two positive integers a and b.
Input: a = 12, b = 15
Input: a = 7, b = 3
Output: 60
Output: 21
Constraints: 1 ≤ a, b ≤ 10^6
Hint: Use formula: lcm(a,b) = (a * b) / gcd(a,b).
Time: O(log min(a,b)) | Space: O(1)
Asked by: Microsoft, Amazon, Intel, IBM
5. Power of Two
Easy
Given an integer n, return true if it is a power of two. Otherwise, return false.
Input: n = 16
Input: n = 3
Output: true (2^4)
Output: false
Constraints: -2^31 ≤ n ≤ 2^31 - 1
Hint: Use bit manipulation: n > 0 && (n & (n-1)) == 0.
Time: O(1) | Space: O(1)
LeetCode #231
Asked by: Google, Apple, Facebook, LinkedIn
6. Power of Three
Easy
Given an integer n, return true if it is a power of three. Otherwise, return false.
Input: n = 27
Input: n = 0
Output: true (3^3)
Output: false
Constraints: -2^31 ≤ n ≤ 2^31 - 1
Hint: Use 1162261467 % n == 0 (largest power of 3 in 32-bit).
Time: O(1) | Space: O(1)
LeetCode #326
Asked by: Google, Microsoft, Amazon
7. Happy Number
Easy
A happy number is defined as: starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat until the number equals 1 (happy) or loops endlessly in a cycle that does not include 1 (not happy).
Input: n = 19
Steps: 1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1
Output: true
Constraints: 1 ≤ n ≤ 2^31 - 1
Hint: Use a set to detect cycles, or use Floyd's cycle detection.
Time: O(log n) | Space: O(log n)
LeetCode #202
Asked by: Google, Microsoft, Uber, Airbnb
8. Ugly Number
Easy
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Input: n = 6
Input: n = 14
Output: true (2×3)
Output: false (2×7)
Constraints: -2^31 ≤ n ≤ 2^31 - 1
Hint: Keep dividing by 2, 3, 5 and check if result is 1.
Time: O(log n) | Space: O(1)
LeetCode #263
Asked by: Google, Amazon, Microsoft
9. Perfect Squares
Medium
Given an integer n, return the least number of perfect square numbers that sum to n.
Input: n = 12
Input: n = 13
Output: 3 (4+4+4)
Output: 2 (4+9)
Constraints: 1 ≤ n ≤ 10^4
Hint: Use dynamic programming or BFS approach.
Time: O(n√n) | Space: O(n)
LeetCode #279
Asked by: Google, Facebook, Amazon, Adobe
10. Factorial Trailing Zeroes
Medium
Given an integer n, return the number of trailing zeroes in n!.
Input: n = 5
5! = 120
Output: 1
Constraints: 0 ≤ n ≤ 10^4
Hint: Count factors of 5 in n!. Each 10 = 2×5, and there are more 2s than 5s.
Time: O(log n) | Space: O(1)
LeetCode #172
Asked by: Google, Microsoft, Apple, Bloomberg
11. Integer to Roman
Medium
Convert an integer to a roman numeral.
Input: num = 3749
Input: num = 58
Output: "MMMDCCXLIX"
Output: "LVIII"
Constraints: 1 ≤ num ≤ 3999
Hint: Use greedy approach with value-symbol pairs in descending order.
Time: O(1) | Space: O(1)
LeetCode #12
Asked by: Facebook, Amazon, Microsoft, Apple
12. Roman to Integer
Easy
Convert a roman numeral to an integer.
Input: s = "LVIII"
Input: s = "MCMXC"
Output: 58
Output: 1990
Constraints: 1 ≤ s.length ≤ 15, s contains only valid roman numerals
Hint: If current symbol < next symbol, subtract current; otherwise add.
Time: O(n) | Space: O(1)
LeetCode #13
Asked by: Facebook, Microsoft, Amazon, Google
13. Excel Sheet Column Number
Easy
Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.
Input: columnTitle = "A"
Input: columnTitle = "AB"
Input: columnTitle = "ZY"
Output: 1
Output: 28
Output: 701
Constraints: 1 ≤ columnTitle.length ≤ 7, columnTitle consists only of uppercase English letters.
Hint: Treat it as base-26 conversion with A=1, B=2, ..., Z=26.
Time: O(n) | Space: O(1)
LeetCode #171
Asked by: Microsoft, Google, Amazon, Facebook