LeetCode 483: Smallest Good Base

Problem Restatement

We are given an integer n as a string.

We need to return the smallest base k such that the representation of n in base k contains only digit 1.

For example:

13 in base 3 = 111

because:

13 = 1 * 3^2 + 1 * 3^1 + 1 * 3^0

So for n = "13", the answer is:

"3"

A good base must satisfy k >= 2. The problem asks for the smallest such base. The examples include 13 -> 3, 4681 -> 8, and 1000000000000000000 -> 999999999999999999.

Input and Output

Function shape:

def smallestGoodBase(n: str) -> str:
    ...

Examples

Example 1:

n = "13"

In base 3:

13 = 1 * 3^2 + 1 * 3^1 + 1
   = 9 + 3 + 1
   = 13

Answer:

"3"

Example 2:

n = "4681"

In base 8:

4681 = 1 + 8 + 8^2 + 8^3 + 8^4
     = 1 + 8 + 64 + 512 + 4096
     = 4681

Answer:

"8"

Example 3:

n = "1000000000000000000"

The answer is:

"999999999999999999"

because in base 999999999999999999, the number is:

11

First Thought: Try Every Base

The direct idea is to try every base k from 2 to n - 1.

For each base, repeatedly divide n by k and check whether every digit is 1.

This is correct, but impossible for large n.

For example, if n = 10^18, checking bases one by one would mean almost 10^18 candidates.

We need to search more mathematically.

Key Insight

If n is written as all ones in base k, then it has this form:

n = 1 + k + k^2 + k^3 + ... + k^m

Here, m + 1 is the number of digits.

So the problem becomes:

Find the smallest integer k >= 2 such that:

n = 1 + k + k^2 + ... + k^m

for some integer m >= 1.

This is a geometric series.

For a fixed m, the sum grows as k grows. That means we can binary search for k.

To get the smallest base, we should try the longest possible representation first.

A longer representation means more digits of 1, which usually requires a smaller base.

For example:

13 = 111 base 3
13 = 11 base 12

Both are valid good bases, but 3 is smaller than 12.

So we test larger digit counts first.

Algorithm

Convert n to an integer:

num = int(n)

The longest possible representation happens in base 2.

So the maximum possible exponent m is roughly:

num.bit_length() - 1

Then loop from large m down to 1.

For each m, we try to find a base k such that:

1 + k + k^2 + ... + k^m = num

For each fixed m:

1. Set left = 2.
2. Set right near the m-th root of num.
3. Binary search for k.
4. Compute the geometric sum carefully.
5. If the sum equals num, return k.

If nothing works, return:

str(num - 1)

This always works because:

num = 1 + (num - 1)

So in base num - 1, the representation is "11".

Correctness

If k is a good base for num, then every digit is 1.

Therefore, for some exponent m >= 1:

num = 1 + k + k^2 + ... + k^m

So every valid answer appears in the search over possible m.

For a fixed m, the function:

f(k) = 1 + k + k^2 + ... + k^m

strictly increases as k increases for all k >= 2.

Therefore, binary search can correctly determine whether there is an integer base k that gives exactly num.

The algorithm checks m from largest to smallest. A larger m means more digits. For the same number, more digits require a smaller base. Therefore, the first valid base found is the smallest good base.

If no representation with at least three digits exists, the two-digit representation always exists:

num = 1 * (num - 1) + 1

So num - 1 is a valid good base. Returning it is correct.

Complexity

Since n <= 10^18, this is very fast.

Implementation

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        num = int(n)

        max_m = num.bit_length() - 1

        for m in range(max_m, 0, -1):
            left = 2
            right = int(num ** (1 / m)) + 1

            while left <= right:
                k = (left + right) // 2

                total = 1
                power = 1

                for _ in range(m):
                    power *= k
                    total += power

                    if total > num:
                        break

                if total == num:
                    return str(k)

                if total < num:
                    left = k + 1
                else:
                    right = k - 1

        return str(num - 1)

Code Explanation

First, convert the input string:

num = int(n)

The input is a string because it may be large, but Python can handle it as an integer.

This finds the largest possible exponent count:

max_m = num.bit_length() - 1

If base is 2, the sum grows slowest, so base 2 gives the longest possible all-ones representation.

Then we try larger digit counts first:

for m in range(max_m, 0, -1):

For each m, we binary search the base:

left = 2
right = int(num ** (1 / m)) + 1

The base cannot be much larger than the m-th root of num, because the term k^m is already part of the sum.

For each candidate base k, compute:

total = 1
power = 1

for _ in range(m):
    power *= k
    total += power

This builds:

1 + k + k^2 + ... + k^m

We stop early if the sum becomes too large:

if total > num:
    break

If the sum equals num, then k is a good base:

if total == num:
    return str(k)

If the sum is too small, we need a larger base.

If the sum is too large, we need a smaller base.

The fallback is:

return str(num - 1)

This corresponds to representation "11".

Testing

def run_tests():
    s = Solution()

    assert s.smallestGoodBase("13") == "3"
    assert s.smallestGoodBase("4681") == "8"
    assert s.smallestGoodBase("1000000000000000000") == "999999999999999999"
    assert s.smallestGoodBase("3") == "2"
    assert s.smallestGoodBase("7") == "2"
    assert s.smallestGoodBase("15") == "2"
    assert s.smallestGoodBase("21") == "4"

    print("all tests passed")

run_tests()

Test meaning: