Problem Description

The Smallest Good Base problem asks: Given an integer n represented as a string, find the smallest good base of n. A good base k (where k >= 2) is such that n can be represented as a sum of the form:

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

for some integer m >= 1 (i.e., all digits in base k are 1). The problem guarantees that there is always exactly one valid solution for each input. The goal is to return the smallest possible k as a string.

• Input: n (string representing a positive integer, up to 10¹⁸)
• Output: Smallest good base k (string)
• Constraints: n is always valid, and there is always one unique answer.

Thought Process

At first glance, one might consider brute-forcing through all possible bases from 2 up to n-1, checking for each if n can be written as a sum of powers of that base. However, this is highly inefficient, especially since n can be as large as 10¹⁸.

The key insight is to recognize that the sum 1 + k + k^2 + ... + k^m is a geometric series. This allows us to relate n, k, and m mathematically, and search for possible values of k much more efficiently.

Instead of checking every possible base, we consider the length of the representation (i.e., how many 1's there are), and for each possible length, we try to find a suitable base using mathematical formulas and binary search.

Solution Approach

• Step 1: Recognize that n = 1 + k + k^2 + ... + k^m = (k^{m+1} - 1) / (k - 1) (geometric sum formula).
• Step 2: For each possible m (number of digits minus one), try to find an integer base k such that the above equation holds.
  • The maximum possible m is floor(log_2 n), since the smallest base is 2 (which gives the longest possible representation).
• Step 3: For each m from largest to smallest, use binary search to find k in the range [2, n^1/m + 1].
  • For each candidate k, compute (k^{m+1} - 1) / (k - 1) and compare to n.
  • If it matches, this k is a good base.
• Step 4: The smallest base found through this process is the answer. If no such base is found, the smallest good base is n-1 (since n = 1 + (n-1) in base n-1).

This approach is efficient because it reduces the number of candidates to check by orders of magnitude and leverages the properties of geometric series and binary search.

Example Walkthrough

Let's take n = "13" as an example.

1. Step 1: Convert n to integer: n = 13.
2. Step 2: Compute max_m = floor(log_2 13) = 3 (since 2^3 = 8, 2^4 = 16 > 13).
3. Step 3: Try m = 3 (4 digits):
   • Possible k in [2, n^1/3 + 1] = [2, 3]
   • Test k = 2: sum = (2^4 - 1) / (2 - 1) = (16 - 1) / 1 = 15
   • Test k = 3: sum = (3^4 - 1) / (3 - 1) = (81 - 1) / 2 = 40
   • Neither equals 13.
4. Step 4: Try m = 2 (3 digits):
   • Possible k in [2, n^1/2 + 1] = [2, 4]
   • Test k = 2: (2^3 - 1) / (2 - 1) = (8 - 1) / 1 = 7
   • Test k = 3: (3^3 - 1) / (3 - 1) = (27 - 1) / 2 = 13
   • Bingo! k = 3 is a good base.
5. Step 5: Since we search from largest m down, the first base found is the smallest good base. Return "3".

Time and Space Complexity

• Brute-force approach:
  • Check all bases from 2 to n-1. For each, simulate the sum. Time complexity: O(n log n), which is infeasible for large n.
• Optimized approach:
  • For each m up to log₂ n (about 60 for n up to 10¹⁸), do a binary search over a small range.
  • Each binary search is over O(log n) steps, and there are O(log n) possible m values.
  • Total time complexity: O((log n)²).
  • Space complexity: O(1), since only a few variables are used.

Code Implementation

import math

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        n = int(n)
        max_m = n.bit_length()  # log2(n), maximum possible m+1
        for m in range(max_m, 1, -1):
            k = int(n ** (1 / (m - 1)))
            if k < 2:
                continue
            # Compute sum = (k^m - 1) // (k - 1)
            s = 1
            curr = 1
            for _ in range(m - 1):
                curr *= k
                s += curr
            if s == n:
                return str(k)
        return str(n - 1)
      

#include <cmath>
#include <string>
using namespace std;

class Solution {
public:
    string smallestGoodBase(string n) {
        unsigned long long num = stoull(n);
        int max_m = log2(num) + 1;
        for (int m = max_m; m >= 2; --m) {
            unsigned long long k = pow(num, 1.0 / (m - 1));
            if (k < 2) continue;
            unsigned long long s = 1, curr = 1;
            for (int i = 1; i < m; ++i) {
                curr *= k;
                s += curr;
            }
            if (s == num) return to_string(k);
        }
        return to_string(num - 1);
    }
};
      

class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        int max_m = (int)(Math.log(num) / Math.log(2)) + 1;
        for (int m = max_m; m >= 2; --m) {
            long k = (long)Math.pow(num, 1.0 / (m - 1));
            if (k < 2) continue;
            long s = 1, curr = 1;
            for (int i = 1; i < m; ++i) {
                curr *= k;
                s += curr;
            }
            if (s == num) return String.valueOf(k);
        }
        return String.valueOf(num - 1);
    }
}
      

var smallestGoodBase = function(n) {
    const num = BigInt(n);
    const max_m = Math.floor(Math.log2(Number(num))) + 1;
    for (let m = max_m; m >= 2; --m) {
        let k = BigInt(Math.floor(Number(num) ** (1 / (m - 1))));
        if (k < 2n) continue;
        let s = 1n, curr = 1n;
        for (let i = 1; i < m; ++i) {
            curr *= k;
            s += curr;
        }
        if (s === num) return k.toString();
    }
    return (num - 1n).toString();
};
      

Summary

The Smallest Good Base problem leverages the geometric series formula to efficiently search for the minimal base in which a number can be represented as a string of all 1's. By iterating over possible lengths of the representation and using binary search (or direct computation) for the base, we avoid brute-force checks and achieve excellent performance. The solution is both mathematically elegant and computationally efficient, making it a great example of combining mathematical insight with programming techniques.