Solution Approach

The implementation uses binary search within a loop to systematically find the smallest good base, following the standard binary search template.

Helper Function calculate_sum(base, num_terms): This function calculates the geometric series sum 1 + base + base² + ... + base^num_terms. It initializes power = 1 (current power of base) and total = 1 (sum starting with the first term). Then it iterates num_terms times, multiplying power by base to get the next power and adding it to the sum.

Main Algorithm:

1. Convert the string n to an integer target for numerical operations.

2. Iterate through possible digit counts m from 63 down to 2:

   • We start from 63 because that's approximately the maximum number of bits needed to represent large integers
   • We check larger m values first because more digits generally means a smaller base

3. For each m, use binary search with the standard template to find the base k:

   • Initialize: left = 2, right = target - 1, first_true_index = -1
   • The feasible condition is calculate_sum(mid, m) >= target
   • Binary search loop: while left <= right
     • Calculate midpoint: mid = (left + right) // 2
     • If feasible(mid): store first_true_index = mid, then search for smaller bases (right = mid - 1)
     • Otherwise: search larger bases (left = mid + 1)

4. After binary search, check if first_true_index != -1 and calculate_sum(first_true_index, m) == target:

   • If yes, we found an exact match! Return str(first_true_index) as the smallest good base for this m
   • If no exact match, continue to the next smaller m

5. If no base is found for any m >= 2, return str(target - 1):

   • This handles the case where m = 1, meaning n = 1 + k
   • Therefore k = n - 1, and n in base (n-1) equals 11

The algorithm efficiently finds the smallest good base by leveraging the monotonic property of the geometric series and using binary search to quickly locate valid bases for each possible digit count.

Example Walkthrough

Let's trace through finding the smallest good base for n = "13" using the standard binary search template.

Step 1: Convert string to integer: target = 13

Step 2: Try different digit counts m from 63 down to 2.

For m = 63, 62, ..., 4:

• When we calculate calculate_sum(2, m) for these values, we get sums much larger than 13
• Binary search finds no exact match for any of these m values
• So we continue to smaller m values

Step 3: When m = 3 (looking for 4 digits):

• Initialize: left = 2, right = 12, first_true_index = -1

• Feasible condition: calculate_sum(mid, 3) >= 13

• First iteration: mid = 7

  • calculate_sum(7, 3) = 1 + 7 + 49 + 343 = 400 >= 13 ✓ (feasible)
  • Update: first_true_index = 7, right = 6

• Second iteration: mid = 4

  • calculate_sum(4, 3) = 1 + 4 + 16 + 64 = 85 >= 13 ✓ (feasible)
  • Update: first_true_index = 4, right = 3

• Third iteration: mid = 2

  • calculate_sum(2, 3) = 1 + 2 + 4 + 8 = 15 >= 13 ✓ (feasible)
  • Update: first_true_index = 2, right = 1

• Loop ends: left > right

• Check: calculate_sum(2, 3) = 15 ≠ 13, so no exact match for m = 3

Step 4: When m = 2 (looking for 3 digits):

• Initialize: left = 2, right = 12, first_true_index = -1

• Feasible condition: calculate_sum(mid, 2) >= 13

• First iteration: mid = 7

  • calculate_sum(7, 2) = 1 + 7 + 49 = 57 >= 13 ✓ (feasible)
  • Update: first_true_index = 7, right = 6

• Second iteration: mid = 4

  • calculate_sum(4, 2) = 1 + 4 + 16 = 21 >= 13 ✓ (feasible)
  • Update: first_true_index = 4, right = 3

• Third iteration: mid = 2

  • calculate_sum(2, 2) = 1 + 2 + 4 = 7 < 13 ✗ (not feasible)
  • Update: left = 3

• Fourth iteration: mid = 3

  • calculate_sum(3, 2) = 1 + 3 + 9 = 13 >= 13 ✓ (feasible)
  • Update: first_true_index = 3, right = 2

• Loop ends: left > right

• Check: calculate_sum(3, 2) = 13 == 13 ✓ Exact match!

Step 5: Return "3"

Indeed, 13 in base 3 equals 111 because 1×3² + 1×3¹ + 1×3⁰ = 9 + 3 + 1 = 13.

Time and Space Complexity

Time Complexity: O(log²(n))

The algorithm iterates through possible lengths m from 63 down to 2, which takes O(log(n)) iterations since the maximum useful value of m is approximately log₂(n). For each value of m, a binary search is performed on the range [2, n-1], which takes O(log(n)) iterations. Within each binary search iteration, the cal function is called, which performs m multiplications and additions, taking O(m) = O(log(n)) time. Therefore, the total time complexity is O(log(n) × log(n) × log(n)) = O(log³(n)).

However, upon closer analysis, the outer loop runs for at most 63 iterations (a constant), so we can consider it as O(1) in terms of n. The binary search takes O(log(n)) iterations, and each call to cal takes O(log(n)) time. This gives us a more precise complexity of O(log²(n)).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space for variables num, m, l, r, mid, and the variables within the cal function (p, s, i). No additional data structures that scale with the input size are used. The input is a string representation of a number, but we only store its integer conversion and a few working variables.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

Incorrect (non-standard template):

while left < right:
    mid = (left + right) // 2
    if calculate_sum(mid, num_terms) >= target:
        right = mid
    else:
        left = mid + 1
return left

Correct (standard template):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid, num_terms, target):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

The standard template with first_true_index clearly tracks whether a valid answer was found and handles edge cases consistently.

2. Integer Overflow in Power Calculation

When base and num_terms are large, computing base^num_terms can exceed the maximum integer value, causing incorrect results or runtime errors.

Solution: Add overflow checking to prevent invalid calculations:

def calculate_sum(base: int, num_terms: int) -> int:
    power = 1
    total = 1
    for _ in range(num_terms):
        if power > (10**18) // base:
            return float('inf')
        power *= base
        total += power
    return total

3. Not Checking for Exact Match

The binary search finds the first base where sum >= target, but we need an exact match where sum == target. Forgetting this check leads to incorrect results.

Solution: After binary search completes, always verify:

if first_true_index != -1 and calculate_sum(first_true_index, num_terms) == target:
    return str(first_true_index)

4. Edge Case: n = "3"

The code returns str(target - 1) when no base is found for m >= 2. This handles m = 1 case where n = 1 + k, giving k = n - 1. For n = "3", this correctly returns "2" since 3 in base 2 is "11".