Combinatorics & Digits

Base Conversion

Converting between bases is the same peel-and-build loop with a different divisor. The interview twist is one-indexed systems like Excel column titles, where A is 1 rather than 0, so you subtract one before each step to make the arithmetic behave.

O(log n)

say this out loud

Same peel-and-build loop with a different divisor. Excel columns are one-indexed with no zero, so I decrement before each step.

How It Works

Base conversion is the digit loop with a different divisor: take n % base for the next digit, then n /= base, and repeat until nothing is left. Digits emerge least significant first, so build into a buffer and reverse once at the end rather than prepending repeatedly, which would make the loop quadratic.

The part that trips people is a system with no zero. Excel column titles run A to Z and then AA, so 26 is Z rather than the AZ-style rollover a normal base-26 system would give. The fix is a single decrement before each step, shifting the one-indexed value into the zero-indexed arithmetic the modulus expects. Converting back reverses it: multiply the running total by 26 and add (c - 'A' + 1) per character. Getting the off-by-one right in both directions is the entire exercise, and it is a common warm-up question because it separates people who reason about the arithmetic from people who pattern-match.

Step-by-Step Visualization

Convert 28 to an Excel column title, where 1 is A, 26 is Z, and 27 is AA

n28

1/7

Code

Java

// Excel: 1 -> A, 26 -> Z, 27 -> AA (one-indexed, no zero digit)
static String toExcelColumn(int n) {
  StringBuilder sb = new StringBuilder();

  while (n > 0) {
    n--;                                  // shift to zero-indexed
    sb.append((char) ('A' + n % 26));
    n /= 26;
  }
  return sb.reverse().toString();
}

Tips & Gotchas

1Same peel-and-build loop as digits, only the divisor changes

2Excel columns are one-indexed with no zero, so decrement before each step

3Build into a StringBuilder and reverse once at the end rather than prepending

Practice Problems

1Excel Sheet Column Title
2Excel Sheet Column Number
3Convert to Base -2
4Base 7
5Add Binary

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

Why is the decrement needed for Excel columns?

Ordinary base-26 has digits 0 to 25, but Excel has A to Z meaning 1 to 26 with no zero at all. Subtracting one before taking the modulus maps the one-indexed value onto the zero-indexed range the arithmetic assumes. Without it, every multiple of 26 comes out wrong.

How does conversion to a negative base work?

The loop is the same, but a negative remainder has to be corrected: add the absolute base to the remainder and add one to the quotient to compensate. It is a good test of whether you understand the loop rather than remembering it, which is why Convert to Base -2 appears in interviews.

Why build and reverse instead of prepending?

Prepending to a String or inserting at index 0 of a StringBuilder shifts every existing character, making the loop O(d^2) in the number of digits. Appending is amortised O(1) and a single reverse at the end is O(d), so the whole conversion stays linear.