Number Theory Basics Explained — Divisibility, Congruence, Digit Problems for Interviews [LC 202, Amazon, Microsoft]

Algorithm Statement#

A toolkit of foundational identities and techniques every interviewer assumes you know:

1. Divisibility: $a \mid b$ means $b = a k$ for some integer $k$. Properties: $a \mid b$ and $a \mid c \Rightarrow a \mid (bx + cy)$.
2. Congruence: $a \equiv b \pmod{m}$ iff $m \mid (a - b)$. Equivalence relation.
3. Digit operations: extract digits with n % 10 and n //= 10; sum, reverse, and check palindromes.
4. Special numbers: perfect, abundant, Armstrong, happy, ugly, Harshad — each defined by a digit or divisor identity.

Constraints typical:

• $1 \le n \le 10^{18}$ for divisibility queries.
• $1 \le n \le 10^9$ for digit DP and special-number checks.

Examples:

divisible(12, 4)      → True       (12 = 4 * 3)
sum_digits(1729)      → 19
is_armstrong(153)     → True       (1^3 + 5^3 + 3^3 = 153)
is_happy(19)          → True       (LC 202)

Why This Problem Matters#

The "easy" tier of number theory hides 30 percent of all interview questions. LC 202 Happy Number, LC 9 Palindrome Number, LC 7 Reverse Integer, LC 263 Ugly Number, LC 504 Base 7, LC 1281 Subtract Product and Sum — every one of these tests divisibility, digit manipulation, and modular reasoning. Amazon and Microsoft especially love these because they can be solved in 10 minutes once the candidate sees the structure, but they crater candidates who never internalised the basics.

This blog consolidates the building blocks: divisibility rules, congruence identities, digit DP scaffolding, and the most common "special number" checks. Get these reflexes solid and the tougher number-theory blogs become straightforward.

The Core Insight#

Divisibility properties. If $a \mid b$ and $a \mid c$, then $a \mid (bx + cy)$ for any integers $x, y$. This linearity drives every divisibility proof. The contrapositive lets you disprove divisibility quickly.

Congruence as equivalence. $\equiv \pmod{m}$ is reflexive, symmetric, and transitive. So you can substitute freely: if $a \equiv a'$ and $b \equiv b'$, then $a + b \equiv a' + b'$ and $ab \equiv a' b'$. This is what makes modular arithmetic compositional.

Digit extraction. In base 10, n % 10 gives the lowest digit and n // 10 strips it. The number of digits is $\lfloor \log_{10} n \rfloor + 1$. To reverse: rev = rev * 10 + n % 10 while peeling.

Sum-of-digits divisibility rules.

• A number is divisible by 3 iff the sum of its digits is divisible by 3.
• Divisible by 9 iff the digit sum is divisible by 9.
• Divisible by 11 iff the alternating digit sum is divisible by 11.
• Divisible by 4 iff the last two digits form a number divisible by 4.

These shortcuts save time in mental check problems.

Perfect / abundant / deficient. Sum the proper divisors $\sigma(n) - n$. Perfect: $\sigma(n) - n = n$. Abundant: greater. Deficient: less. The first few perfect numbers are 6, 28, 496, 8128.

Armstrong (narcissistic). $n$ equals the sum of its digits each raised to the power of the digit count.

Happy. Repeatedly replace $n$ by the sum of squares of its digits. If the sequence reaches 1, the number is happy. Otherwise it cycles (Floyd's algorithm detects the cycle).

Visual Dry Run#

Check whether 19 is a happy number (LC 202).

n = 19
  squares: 1^2 + 9^2 = 1 + 81 = 82
n = 82
  squares: 64 + 4 = 68
n = 68
  squares: 36 + 64 = 100
n = 100
  squares: 1 + 0 + 0 = 1
n = 1  → Happy!

Apply Floyd's tortoise-and-hare to detect cycle:

slow = digit_square_sum(slow)
fast = digit_square_sum(digit_square_sum(fast))
If slow == 1 → return True
If slow == fast and slow != 1 → return False (cycle)

Reverse 12345.

n = 12345, rev = 0
  rev = 0  * 10 + 5  = 5    n = 1234
  rev = 5  * 10 + 4  = 54   n = 123
  rev = 54 * 10 + 3  = 543  n = 12
  rev = 543* 10 + 2  = 5432 n = 1
  rev = 5432 * 10 + 1 = 54321

Solution (Optimal)#

Python#

# 1. Sum of digits
def sum_digits(n: int) -> int:
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s
 
# 2. Reverse digits
def reverse_int(n: int) -> int:
    sign = -1 if n < 0 else 1
    n = abs(n)
    rev = 0
    while n > 0:
        rev = rev * 10 + n % 10
        n //= 10
    return sign * rev
 
# 3. Palindrome (without converting to string)
def is_palindrome(n: int) -> bool:
    if n < 0: return False
    return n == reverse_int(n)
 
# 4. Happy number (LC 202)
def is_happy(n: int) -> bool:
    def square_sum(x):
        s = 0
        while x:
            s += (x % 10) ** 2
            x //= 10
        return s
    slow, fast = n, square_sum(n)
    while fast != 1 and slow != fast:
        slow = square_sum(slow)
        fast = square_sum(square_sum(fast))
    return fast == 1
 
# 5. Armstrong check
def is_armstrong(n: int) -> bool:
    digits = [int(d) for d in str(n)]
    k = len(digits)
    return sum(d**k for d in digits) == n

Complexity: Each helper is $O(\log_{10} n)$ in time and $O(1)$ space.

JavaScript#

function sumDigits(n) {
    let s = 0;
    while (n > 0) { s += n % 10; n = Math.floor(n / 10); }
    return s;
}
 
function reverseInt(n) {
    const sign = n < 0 ? -1 : 1;
    n = Math.abs(n);
    let rev = 0;
    while (n > 0) {
        rev = rev * 10 + n % 10;
        n = Math.floor(n / 10);
    }
    return sign * rev;
}
 
function isHappy(n) {
    const sq = x => {
        let s = 0;
        while (x) { s += (x % 10) ** 2; x = Math.floor(x / 10); }
        return s;
    };
    let slow = n, fast = sq(n);
    while (fast !== 1 && slow !== fast) {
        slow = sq(slow);
        fast = sq(sq(fast));
    }
    return fast === 1;
}

Common Mistakes#

1. Integer overflow when reversing. A 32-bit signed int can hold |n| < 2^{31}. The reverse of a 10-digit number can exceed that bound. Check before each multiplication.
2. Negative modulo behaviour. In C, C++, Java, and JavaScript, -7 % 3 = -1, not $2$. Add the modulus before reducing.
3. Treating happy-number iteration as unbounded. Use Floyd's cycle detection, hash-set tracking, or the known fact that any unhappy number falls into the cycle {4, 16, 37, 58, 89, 145, 42, 20}.
4. Off-by-one in digit count. $\lfloor \log_{10} 0 \rfloor$ is undefined; treat $n = 0$ as one digit.
5. String shortcuts on huge integers. Converting to a string costs an allocation; for hot paths, use the integer arithmetic version.
6. Forgetting the leading digit. When reversing, the loop continues while $n > 0$, never $n \ge 0$ — otherwise it loops forever.

Interview Tips#

• Lead with divisibility intuition: "I will check divisibility by 3 via the digit sum to avoid expensive modulo on big numbers."
• For happy / ugly / Armstrong problems, mention the cycle property up front. It signals you have seen the pattern before.
• For palindromic numbers, reverse only half — once rev >= n, you have processed enough digits.
• When the problem says "do not convert to string", do not. Use modular arithmetic.

Follow-up Questions#

Q1: Count integers in $[1, n]$ divisible by neither 3 nor 5. A: By inclusion-exclusion, the count is $n - \lfloor n/3 \rfloor - \lfloor n/5 \rfloor + \lfloor n/15 \rfloor$.

Q2: Why is divisibility by 3 equivalent to digit-sum divisibility by 3? A: $10 \equiv 1 \pmod 3$, so $\sum d_i 10^i \equiv \sum d_i \pmod 3$.

Q3: Detect a cycle in the happy-number sequence in $O(1)$ space. A: Use Floyd's tortoise-and-hare on the iterating function. The cycle exists for every starting input.

Q4: Generate the next palindrome greater than $n$. A: Mirror the left half of $n$. If the result is $\le n$, increment the middle and propagate carry, then mirror again.

Key Takeaways#

• Divisibility is linear: $a \mid b$ and $a \mid c$ imply $a$ divides every integer combination of $b$ and $c$.
• Congruence is an equivalence relation, so you can add, subtract, and multiply on both sides freely under a fixed modulus.
• Memorise the digit-sum divisibility rules (3, 9, 11) — they convert hot-path mod checks into $O(\log n)$ digit walks.
• For happy / ugly / Armstrong checks, use cycle detection (Floyd's or a small hash set) and lean on the closed-form properties.
• Keep digit operations pure-integer to avoid string allocation on tight loops.
• Whenever a problem says "modulo $10^9 + 7$", switch to modular addition, multiplication, and inverse — never use floating-point division.