Problem 483

Abstract / Summary

Find the smallest base so that a number can be written as a string of the same digit repeated at least twice.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0483.py

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        n = int(n)
        result = n - 1 # each number n has good base n - 1

        # n = k^i + k^(i-1) + k^(i-2) + ... + k^2 + k + 1
        for i in range(2, 64):    # 10^18 < 2^64
            k = floor(n**(1 / i)) # i-th root of n
            if k == 1:
                break

            s = sum(k**j for j in range(i + 1))
            if s == n:
                result = k

        return str(result)
16 lines | 488 bytes | submitted September 30, 2023 | GitHub   33% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 46% (60k+ submissions).

Typical patterns to solve this problem:
  • Binary Search
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the smallest “good base” for a given positive integer supplied as a string. A good base k for a number n satisfies the equation

n = kⁱ + kⁱ⁻¹ + … + k + 1

for some integer exponent i ≥ 2. The algorithm searches for the smallest base that fulfills this representation, falling back to the trivial base n - 1 when no smaller base exists.

Parsing the Input

n = int(n)

The function begins by converting the input string to an integer, enabling arithmetic operations throughout the remainder of the routine.

Establishing a Default Result

result = n - 1  # each number n has good base n - 1

Because any integer n can always be expressed as a sum of n terms of 1 (i.e., base n - 1), the algorithm initializes the answer with this guaranteed value. This default ensures that the function always returns a valid base, even when no smaller representation is found.

Enumerating Possible Lengths of the Representation

for i in range(2, 64):    # 10^18 < 2^64

The loop iterates over candidate lengths i of the geometric series, starting at 2 because a length of 1 would correspond to the trivial representation. The upper bound of 64 is chosen because the problem constraints guarantee that the input does not exceed 10¹⁸, and any exponent larger than 63 would produce a base smaller than 2, which is impossible for a good base.

Approximating the Candidate Base

k = floor(n**(1 / i))  # i-th root of n
if k == 1:
    break

For each exponent i, the algorithm computes the integer floor of the i-th root of n, which serves as a candidate base k. If the root collapses to 1, the loop terminates early because any larger exponent would also yield a base of 1, which cannot satisfy the required sum for n > 2. This early exit prevents unnecessary iterations.

Verifying the Geometric Sum

s = sum(k**j for j in range(i + 1))
if s == n:
    result = k

The candidate base k is validated by constructing the full geometric series of length i + 1 and comparing its sum to the original number n. The generator expression computes each power kʲ on demand, and the built-in sum aggregates them efficiently. When the sum matches n, the algorithm records k as the current smallest good base.

Handling Edge Cases

When the input number is very small (for example, n = 2 or n = 3), the i-th root quickly reduces to 1. The early break condition captures this situation, leaving the default result n - 1 as the correct answer. Similarly, for numbers that are powers of two minus one (such as 7 = 2³ - 1), the loop discovers the appropriate base 2 when i matches the exponent of the underlying power, overriding the default.

Performance Optimizations

The algorithm limits the search space by capping the exponent at 63, which aligns with the maximum size of the input and eliminates needless checks beyond that range. The early termination when the candidate base becomes 1 further reduces the number of iterations for small inputs. By using the built-in sum function together with a generator expression, the code leverages Python’s optimized internal loops, minimizing overhead for the modest number of terms (at most 64) evaluated in each iteration.

Final Result

return str(result)

The function concludes by converting the integer base back to a string, matching the expected return type. This final step delivers the smallest good base discovered during the search, or the fallback base n - 1 when no smaller representation exists.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a giant pile of building blocks that you want to stack into a perfectly level tower. This code is like a clever helper trying to figure out how to arrange those blocks so they form a beautiful, even shape.

First, the code takes the total number of blocks provided and turns it into a real number it can count. It starts with the simplest idea, which is making a very wide tower that is only two layers tall. This is always a safe way to start.

Then, the helper begins a game of guessing. It tries out different tower heights, starting with three layers and going all the way up to sixty-three layers. For each height, it looks at the total number of blocks and calculates exactly how many blocks need to go in each row to reach that specific height perfectly. It uses a bit of math to find the right root, which is like figuring out the size of the base needed to make the tower fit the pile of blocks you have.

The code checks if adding up those rows matches the total number of blocks in the pile. If the math adds up perfectly, it remembers that size as the new best base because it is always looking for the smallest one. It keeps trying different heights until it is sure it has found the tiniest possible base that makes the whole pile stack up without any blocks left over.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 5.93 | σ = 1.82

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
everthis JS
halfrost Go
JoshCrozier JS
linouk23 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
wisdompeak C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Java, Python
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
halfrost Go
JoshCrozier JavaScript
linouk23 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
wisdompeak C++
zfang399 C++
27 links | 16 authors | 8 languages

Videos

3 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

1 medium 3 hard
5 solutions   September 30, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality