Skip to main content
Talentd

Smallest Good Base - Solution & Explanation

HardMathBinary Search8 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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.

 

Example 1:

Input: n = "13"
Output: "3"
Explanation: 13 base 3 is 111.

Example 2:

Input: n = "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

Example 3:

Input: n = "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

 

Constraints:

  • n is an integer in the range [3, 1018].
  • n does not contain any leading zeros.

Approach Overview

Problem Overview: Given a number n (as a string), find the smallest base k ≥ 2 such that n written in base k consists only of 1s. In other words, n = 1 + k + k^2 + ... + k^m for some m ≥ 1. The challenge is that n can be very large, so brute forcing bases is not practical.

Approach 1: Binary Search for Base Length (O((log n)^2) time, O(1) space)

The representation 111...1 in base k forms a geometric series: n = (k^(m+1) - 1) / (k - 1). Instead of guessing the base directly, iterate over the possible length m + 1 of the representation. The maximum length occurs when k = 2, which gives about log2(n) digits. For each candidate length, run a binary search on the base k. During the search, compute the geometric sum incrementally to avoid overflow. If the sum equals n, that base is valid. Because the outer loop runs about log n times and each binary search also takes log n, the total complexity is roughly O((log n)^2). This approach is reliable and handles very large values cleanly.

Approach 2: Iterative Check on Powers (O((log n)^2) time, O(1) space)

Another way is to iterate over possible lengths of the representation and directly estimate the base using powers. For a sequence of m + 1 ones, the base is approximately k ≈ n^(1/m). Compute this candidate base using floating point, then verify it by reconstructing the sum 1 + k + k^2 + ... + k^m. The verification step uses integer multiplication to avoid precision issues. If the computed sum equals n, that base is valid. This method avoids explicit binary search but still relies on checking up to log n possible lengths and performing O(m) multiplication steps for validation.

Both approaches rely heavily on properties of geometric progressions and large integer arithmetic, which makes the problem primarily a math and binary search exercise rather than a typical data structure problem. Care must be taken to stop multiplication early if the partial sum exceeds n, preventing overflow and unnecessary work.

Recommended for interviews: The binary search on base length is the approach most interviewers expect. It demonstrates that you recognize the geometric series pattern and know how to combine mathematical insight with binary search. Explaining the maximum length bound (log2(n)) shows deeper reasoning. The iterative power-check method is also valid, but binary search communicates stronger algorithmic thinking.

Approach 1: Binary Search for Base Length

We aim to find the smallest base k for which the number n can be represented as all 1's. This implies that n can be written as 1 + k + k^2 + k^3 + ... + k^(m-1) for some integer m. We can perform a binary search over possible values of m, since the maximum number of terms for which the number is strictly increasing is log2(n) + 1.

This Python solution leverages the binary search technique by iterating over possible lengths of all '1's representation (from highest to lowest). For each possible m, it computes the possible base k by taking the m-1 root of n and checks if the series sum equals n.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(log(n) * log(n)) due to iterating over possible values of m and calculating powers.
Space Complexity: O(1) because only a constant amount of space is used.

Try this approach in the editor →

Approach 2: Iterative Check on Powers

We can directly iterate and check powers of each candidate base from 2 up to the number n-1. In each iteration, try building the number n by forming a geometric series with base k.

This Java solution uses embedding within a power loop to efficiently construct and check each attempted number long k against the target n.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n log n), dependent on iterating over possible base values and depth of power calculation.
Space Complexity: O(1), given only scalars are maintained.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search for Base Length

Time Complexity: O(log(n) * log(n)) due to iterating over possible values of m and calculating powers.
Space Complexity: O(1) because only a constant amount of space is used.

Iterative Check on Powers

Time Complexity: O(n log n), dependent on iterating over possible base values and depth of power calculation.
Space Complexity: O(1), given only scalars are maintained.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search for Base LengthO((log n)^2)O(1)Best general solution for very large n; stable and precise using integer checks
Iterative Check on PowersO((log n)^2)O(1)When estimating the base via n^(1/m) is simpler to implement and precision checks are manageable

Video Solution

483. Smallest Good Base | leetcode | Binary Search Approach • Ashwani Kansal • 2,783 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Smallest Good Base easy or hard?
Smallest Good Base is classified as a Hard problem. The difficulty comes from recognizing the geometric series representation and efficiently searching the base space using logarithmic bounds rather than brute force.
Smallest Good Base Python/Java solution
Python, Java, C++, and JavaScript implementations typically iterate over possible digit lengths and check whether a base satisfies the geometric series sum. Python solutions often use integer arithmetic with loops, while Java and C++ versions must guard against overflow when multiplying powers.
How to solve Smallest Good Base in O(n)?
An O(n) approach is not practical because n can be extremely large (up to 10^18). Instead, efficient solutions rely on logarithmic bounds. By limiting the number of digits to log2(n) and checking bases using binary search or power validation, the problem is solved in about O((log n)^2) time.
What is the best approach for Smallest Good Base?
The most reliable approach is iterating over possible representation lengths and performing binary search on the base. The equation n = 1 + k + k^2 + ... + k^m forms a geometric series, so binary search helps find the base efficiently. This method runs in about O((log n)^2) time and constant space while safely handling very large numbers.
Is Smallest Good Base asked at Google/Amazon/Meta?
Smallest Good Base is a classic math-heavy interview problem that appears in advanced algorithm rounds at companies like Google and occasionally Amazon. It tests mathematical reasoning, geometric series manipulation, and careful handling of large integers rather than standard data structures.
What data structure is used in Smallest Good Base?
The problem does not rely on complex data structures. It mainly uses mathematical formulas, exponentiation, and binary search. The focus is on evaluating geometric series and preventing overflow while checking candidate bases.
What is the time complexity of Smallest Good Base?
The optimal solutions run in approximately O((log n)^2) time with O(1) space. There are up to log2(n) possible lengths of the representation, and for each length the algorithm either performs a binary search on the base or validates the geometric sum using iterative multiplication.

Ready to solve this problem?

Practice Smallest Good Base with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer