LeetCode 483: Smallest Good Base Solution in Python – A Step-by-Step Guide

What Is LeetCode 483: Smallest Good Base?

In LeetCode 483: Smallest Good Base, you’re given a string n representing a positive integer, and your task is to find the smallest base ( k ) (( k \geq 2 )) such that ( n ) can be expressed as a sum of powers of ( k ) with all coefficients equal to 1—i.e., ( n = 1 + k + k^2 + \dots + k^m ) for some integer ( m )—and return ( k ) as a string. This ( k ) is called a "good base." For example, for n = "13", the smallest good base is "3" because ( 13 = 1 + 3 + 9 ), and no smaller base works. It’s like finding the tiniest building block that stacks perfectly into your number with only 1s.

Problem Statement

• Input: n (str)—positive integer as a string.
• Output: str—smallest good base \( k \) as a string.
• Rules:
• \( n = 1 + k + k^2 + \dots + k^m \) for some \( m \geq 0 \).
• \( k \geq 2 \), integer.
• \( k \) must be the smallest possible base.

Constraints

• \( 1 \leq n < 10^{18} \) (given as a string to handle large numbers).
• \( n \) has no leading zeros.

Examples to Get Us Started

• Input: n = "13"
• Output: "3" (\( 13 = 1 + 3 + 9 = 1 + 3^1 + 3^2 \)).
• Input: n = "3"
• Output: "2" (\( 3 = 1 + 2 = 1 + 2^1 \)).
• Input: n = "4681"
• Output: "8" (\( 4681 = 1 + 8 + 64 + 512 + 4096 = 1 + 8^1 + 8^2 + 8^3 + 8^4 \)).

Understanding the Problem: Unearthing the Base

To solve LeetCode 483: Smallest Good Base in Python, we need to find the smallest integer ( k \geq 2 ) such that ( n ) equals a geometric series of the form ( 1 + k + k^2 + \dots + k^m ), then return ( k ) as a string. A naive approach—testing every ( k ) from 2 upwards—could be O(\sqrt{n}) or worse, impractical for ( n = 10^{18} ). The key? Use the geometric series formula and binary search to efficiently find ( k ) for each possible length ( m ), leveraging the fact that ( k^m \approx n ). We’ll explore:

• Best Solution (Binary Search with Geometric Series): O(log² n) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force Enumeration): O(\sqrt{n}) time, O(1) space—simple but slow.

Let’s dive into the binary search solution—it’s the explorer’s precise compass we need.

Best Solution: Binary Search with Geometric Series

Why This Is the Best Solution

The binary search with geometric series approach is the top pick because it’s O(log² n) time and O(1) space, efficiently finding the smallest good base by iterating over possible lengths ( m ) (from 1 to log₂(n)) and using binary search to find the corresponding ( k ) that satisfies ( n = (k^{m+1} - 1) / (k - 1) ). It avoids exhaustive enumeration by leveraging the geometric series formula and logarithmic bounds. It’s like using a treasure map to pinpoint the smallest base with precision—smart and swift!

How It Works

Here’s the strategy:

• Step 1: Convert \( n \) to integer, set bounds:
• \( m \) from 1 to floor(log₂(n)) (max terms possible).
• Step 2: For each \( m \) (length - 1):
• Solve \( n = (k^{m+1} - 1) / (k - 1) \) for integer \( k \).
• Use binary search on \( k \) from 2 to \( n^{1/m} \).
• Check if sum matches \( n \).
• Step 3: Return smallest \( k \) found as string.
• Why It Works:
• Geometric series: \( 1 + k + k^2 + \dots + k^m = (k^{m+1} - 1) / (k - 1) \).
• Binary search finds exact \( k \) per \( m \), smallest \( m \) gives smallest \( k \).

Step-by-Step Example

Example: n = "13"

• n = 13, max \( m = \lfloor \log_2(13) \rfloor = 3 \).
• m = 1: \( 1 + k = 13 \), \( k = 12 \), valid.
• m = 2: \( 1 + k + k^2 = 13 \):
• Binary search \( k \): 2 to \( 13^{1/2} \approx 3.6 \):
• \( k = 3 \): \( 1 + 3 + 9 = 13 \), valid.
• \( k = 2 \): \( 1 + 2 + 4 = 7 < 13 \).
• m = 3: \( 1 + k + k^2 + k^3 = 13 \):
• Max \( k \approx 13^{1/3} \approx 2.35 \), \( k = 2 \): \( 1 + 2 + 4 + 8 = 15 > 13 \), no integer.
• Smallest \( k \): 3 (m=2).
• Result: "3".

Example: n = "3"

• m = 1: \( 1 + k = 3 \), \( k = 2 \), valid.
• Result: "2".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeimport math

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        # Step 1: Convert n to int, set max m
        n = int(n)
        max_m = int(math.log2(n))

        # Step 2: Try each m from max to 1
        for m in range(max_m, 0, -1):
            # Binary search for k
            left, right = 2, int(n ** (1 / m)) + 1
            while left < right:
                mid = left + (right - left) // 2
                # Compute sum: (k^(m+1) - 1) / (k - 1)
                curr_sum = 0
                for i in range(m + 1):
                    if curr_sum > n:  # Overflow check
                        break
                    curr_sum = curr_sum * mid + 1
                if curr_sum == n:
                    return str(mid)
                elif curr_sum < n:
                    left = mid + 1
                else:
                    right = mid

        # Fallback (n-1 is always a base for n >= 3)
        return str(n - 1)

• Line 6-7: Convert n, compute max \( m = \lfloor \log_2(n) \rfloor \).
• Line 10-23: For each \( m \):
• Binary search \( k \) from 2 to \( n^{1/m} \).
• Compute sum iteratively (avoid overflow).
• If sum = n, return \( k \).
• Adjust search bounds.
• Line 26: Fallback: \( n-1 \) works (e.g., 3 = 1 + 2).
• Time Complexity: O(log² n)—log n for \( m \), log n for binary search.
• Space Complexity: O(1)—minimal space.

It’s like a base-finding compass!

Alternative Solution: Brute Force Enumeration

Why an Alternative Approach?

The brute force enumeration—O(\sqrt{n}) time, O(1) space—tests all ( k ) from 2 to ( \sqrt{n} ), computing the geometric sum for each and checking if it equals ( n ). It’s slow but intuitive, like digging through every base with a shovel. Good for small ( n ) or learning!

How It Works

• Step 1: Iterate \( k \) from 2 to \( \sqrt{n} \).
• Step 2: For each \( k \), compute sum until ≥ n.
• Step 3: If sum = n, return \( k \).
• Step 4: Return smallest found.

Step-by-Step Example

Example: n = "13"

• k = 2: \( 1 + 2 = 3 \), \( 1 + 2 + 4 = 7 \), \( 1 + 2 + 4 + 8 = 15 > 13 \), no.
• k = 3: \( 1 + 3 = 4 \), \( 1 + 3 + 9 = 13 \), valid, stop.
• Result: "3".

Code for Brute Force

Copy codeclass Solution:
    def smallestGoodBase(self, n: str) -> str:
        n = int(n)
        for k in range(2, int(n ** 0.5) + 1):
            curr_sum = 0
            power = 0
            while curr_sum < n:
                curr_sum += k ** power
                power += 1
                if curr_sum == n:
                    return str(k)
        return str(n - 1)  # Fallback

• Line 4-11: Test each \( k \), compute sum, return if match.
• Line 12: Fallback \( n-1 \).
• Time Complexity: O(\sqrt{n} * log n)—sqrt(n) bases, log n powers.
• Space Complexity: O(1)—minimal space.

It’s a slow base digger!

Comparing the Two Solutions

• Binary Search (Best):
• Pros: O(log² n), fast, scalable.
• Cons: Math-heavy logic.
• Brute Force (Alternative):
• Pros: O(\sqrt{n}), simple.
• Cons: Slow for large n.

Binary search wins for efficiency.

Edge Cases and Examples

• Input: "1" → "2" (debatable, but n-1 fallback).
• Input: "1000000000000000000" → "999999999999999999".
• Input: "15" → "4" (\( 15 = 1 + 4 + 4^2 \)).

Binary search handles all well.

Complexity Recap

• Binary Search: Time O(log² n), Space O(1).
• Brute Force: Time O(\sqrt{n} * log n), Space O(1).

Binary search’s the champ.

Key Takeaways

• Binary Search: Pinpoint with math.
• Brute Force: Test all bases.
• Python Tip: Math optimizes—see [Python Basics](/python/basics).

Final Thoughts: Find That Base

LeetCode 483: Smallest Good Base in Python is a base-hunting numerical quest. Binary search with geometric series is your fast compass, while brute force is a slow shovel. Want more math challenges? Try LeetCode 50: Pow(x, n) or LeetCode 372: Super Pow. Ready to unearth some bases? Head to Solve LeetCode 483 on LeetCode and dig it today—your coding skills are base-ready!