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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Good Base

Difficulty: Hard

Problem Description

Given an integer n represented as a string, return the smallest good base of n. We call k >= 2 a good base of n, if all digits of n base k are 1's.

Key Insights

  • A good base k satisfies the condition that n can be expressed as a sum of powers of k, specifically n = k^m + k^(m-1) + ... + k^0, where all coefficients are 1.
  • The maximum possible value of m can be derived from the logarithm of n, since k^(m+1) > n for k >= 2.
  • By iterating possible values of m from a maximum down to 1, we can calculate the corresponding k using the formula derived from the geometric series.

Space and Time Complexity

Time Complexity: O(log(n)) Space Complexity: O(1)

Solution

The problem can be solved using a mathematical approach where we calculate potential values for k based on m. We iterate m from its maximum possible value down to 1 and derive k using the formula for the sum of a geometric series. The first valid k found will be the smallest good base.

Code Solutions

def smallestGoodBase(n: str) -> str:
    num = int(n)
    max_m = int(num.bit_length())  # Maximum possible value of m

    for m in range(max_m, 1, -1):
        # Calculate k using the formula derived from the geometric series
        k = int(num ** (1/m))
        # Check if it forms the correct series
        if (k**(m+1) - 1) // (k - 1) == num:
            return str(k)

    return str(num - 1)  # The case where k = num - 1
← Back to All Questions