We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Good Base

Number: 483

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an integer n represented as a string, find the smallest integer base k (with k >= 2) such that n can be expressed as a sequence of ones in base k. That is, n = 1 + k + k² + … + k^m for some m >= 1.

Key Insights

  • n expressed in a good base k has the form: n = (k^(m+1) - 1) / (k - 1), meaning its base-k representation consists solely of 1's.
  • Rearranging the equation leads naturally to iterating over possible values of m (where m+1 is the number of digits).
  • The maximum possible m is roughly floor(log₂(n)) because when k = 2 the sum is smallest.
  • For a given m, we can binary search for a candidate base k in the range [2, floor(n^(1/m)) + 1].
  • Be careful with large numbers and potential overflows when computing powers or sums.

Space and Time Complexity

Time Complexity: O((log n)^2 * poly(log n)) since we iterate over possible m values and perform binary search for each m. Space Complexity: O(1)

Solution

The approach is to iterate over possible values of m (starting from the largest possible based on log₂(n) and decreasing). For each m, we perform a binary search for the candidate base k in the interval [2, floor(n^(1/m)) + 1]. For each candidate k, we compute the geometric series sum = 1 + k + k² + … + k^m carefully to see if it equals n. If the sum matches n, then we have found the smallest good base. If none of the m values yield a valid k, then n can only be expressed as "11" in base (n - 1), so the answer is n - 1.

Code Solutions

def smallestGoodBase(n: str) -> str:
    num = int(n)
    import math
    # Maximum m is floor(log2(num))
    max_m = int(math.log(num, 2))
    
    # Try all possible m in descending order
    for m in range(max_m, 0, -1):
        # k must be between 2 and num^(1/m)
        k_low = 2
        k_high = int(num ** (1 / m)) + 1
        while k_low <= k_high:
            k_mid = (k_low + k_high) // 2
            total = 1
            curr = 1
            for _ in range(m):
                curr *= k_mid
                total += curr
                if total > num:
                    break
            if total == num:
                return str(k_mid)
            elif total < num:
                k_low = k_mid + 1
            else:
                k_high = k_mid - 1
    # Fallback if no valid base found
    return str(num - 1)

# Example usage:
print(smallestGoodBase("13"))
← Back to All Questions