Combinatorics & Digits

Digit Manipulation

Peel digits with n % 10 and n /= 10. That covers digit sums, reversing a number, palindrome checks without strings, and digital roots. Watch for overflow when rebuilding a reversed int, and check the sign before you start.

O(log n)

O(1)

say this out loud

n mod ten peels the last digit and n over ten drops it. When rebuilding a reversed number I check against the limit before multiplying, not after.

How It Works

Digit problems reduce to two operations: n % 10 gives the last digit and n /= 10 removes it. Loop until n is zero and you have visited every digit from least significant to most. That covers digit sums, digital roots, palindrome checks and reversal without ever converting to a string.

The interview content is almost entirely in the edge cases. Reversing an int can overflow even when the input is valid, since 1534236469 reverses to a value beyond Integer.MAX_VALUE, so check result against Integer.MAX_VALUE / 10 before each multiply rather than after, when the damage is already done. Negative numbers need the sign handled up front, and in Java the % operator keeps the sign of the dividend, which is convenient here but differs from Python. For palindromes, reversing only half the number and comparing against the remaining half avoids the overflow question entirely, which is the intended solution to the classic problem.

Step-by-Step Visualization

Reverse 1234

x1234

result0

1/5

Code

Java

static int reverse(int x) {
  int result = 0;

  while (x != 0) {
    int digit = x % 10;
    x /= 10;

    // overflow check before the shift, not after
    if (result > Integer.MAX_VALUE / 10) return 0;
    if (result < Integer.MIN_VALUE / 10) return 0;

    result = result * 10 + digit;
  }
  return result;
}

Tips & Gotchas

1n % 10 peels the last digit, n /= 10 drops it. That is the whole toolkit

2Reversing an int can overflow: check against Integer.MAX_VALUE / 10 before each push

3Compare a reversed half against the remaining half to test palindromes without strings

Practice Problems

1Reverse Integer
2Palindrome Number
3Add Digits
4Plus One
5Happy Number

About the Combinatorics & Digits Pattern

Counting problems and digit problems share a habit: the naive formula overflows or the naive loop is too slow, and the fix is to reorganise the arithmetic rather than reach for a bigger integer type.

Key insight

Almost every math problem is asking you to avoid the obvious loop. Trial division to n becomes a sieve, repeated multiplication becomes binary exponentiation, and division under a modulus becomes multiplication by an inverse. If your solution loops to n or to the exponent, there is nearly always a log or sqrt version.

Common Math & Number Theory Interview Problems

Count Primes
Pow(x, n)
Greatest Common Divisor of Strings
Excel Sheet Column Title
Ugly Number II
Factorial Trailing Zeroes

Frequently Asked Questions

How do I detect overflow before it happens?

Compare the accumulator against Integer.MAX_VALUE / 10 before multiplying by 10. If it is already larger, the next step must overflow. Checking afterwards is useless, because signed overflow in Java wraps silently rather than throwing, so the corrupted value looks legitimate.

Why reverse only half the number for a palindrome check?

Reversing the whole number can overflow for inputs that are otherwise fine. Instead build the reversed half while shrinking the original, and stop when the reversed part is at least as large as what remains. Then compare, allowing for a middle digit on odd lengths, and no overflow is possible.

What is the O(1) trick for repeated digit sums?

The digital root of n is 1 + (n - 1) % 9 for positive n, because a number is congruent to its digit sum modulo 9. That replaces the loop in Add Digits with a single expression, and the modulo 9 property is worth remembering for divisibility questions generally.