Smallest Good Base

Smallest Good Base

What is this problem about?

The "Smallest Good Base" interview question is a sophisticated math and binary search problem. A "good base" k for a number n is a base such that all digits of n in base k are '1'. For example, 13 in base 3 is 111 because 13 = 3^2 + 3^1 + 3^0. You need to find the smallest such base k >= 2. This "Smallest Good Base coding problem" requires solving the equation n = k^m + k^(m-1) + ... + k^1 + k^0 for the smallest k.

Why is this asked in interviews?

Google and Microsoft ask this because it combines number theory (geometric series) with search optimization. It tests if a candidate can represent a number as a sum of powers and realize that a smaller base k implies a larger number of digits m. Since we want the smallest base, we should search for the maximum possible number of digits first. It evaluates high-level mathematical intuition and precision in implementation.

Algorithmic pattern used

This follows the "Math and Binary Search interview pattern".

1. The equation n = (k^(m+1) - 1) / (k - 1) describes a geometric series.
2. The number of digits m can range from approximately 60 (for base 2) down to 1.
3. Iterate through possible values of m from 60 down to 2.
4. For each m, use binary search to find a base k such that the series sum equals n.
5. The first k we find for the largest m will be our smallest base.

Example explanation

Let n = 31.

1. Try m = 4 (5 digits): k^4 + k^3 + k^2 + k^1 + k^0 = 31. If k=2, 16+8+4+2+1 = 31.
2. Base 2 is a good base. Since we started with the largest possible m, 2 is likely the smallest base. If n = 13, m=2 gives k^2 + k + 1 = 13. Solving k^2 + k - 12 = 0 gives k = 3.

Common mistakes candidates make

A common error is not correctly identifying the bounds for m. Another frequent mistake is overflow; when calculating k^m, the values can easily exceed the limits of a 64-bit integer. Candidates often fail to use binary search for k and try to solve the polynomial directly, which is much harder. Finally, forgetting the base case where k = n - 1 (representing n as 11 in base n-1) is a common oversight.

Interview preparation tip

For "HARD" math problems, try to identify the variables you can iterate over. Here, iterating over the number of digits m (which is small) is much better than iterating over the base k (which is large). This "Smallest Good Base interview question" is a classic example of reducing search space through mathematical observation.