What is the time complexity of the Smallest Good Base problem?

The time complexity is O(log n) due to the binary search over the possible base values k.

How can I optimize my solution for the Smallest Good Base problem?

By using binary search, you can optimize the solution to efficiently find the smallest base without checking every possible value.

What is a 'good base' in the context of this problem?

A good base is one where the number n, when represented in that base, consists entirely of 1's.

Can you explain how binary search is applied in the Smallest Good Base problem?

Binary search is used to find the smallest base k such that n can be represented as all 1's in base k. The search range is between 2 and n-1, and each iteration checks the validity of the base.

What are common mistakes when solving the Smallest Good Base problem?

Common mistakes include misinterpreting the mathematical relationship between n and k, or failing to implement the binary search correctly, which may lead to incorrect answers or inefficient solutions.

#483

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

最小好进制

以字符串的形式给出 n , 以字符串的形式返回 n 的最小好进制。如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个好进制。示例 1：输入： n = "13" 输出： "3" 解释： 13 的 3 进制是 111。示例 2：输入： n = "…

数学二分查找

题目描述

以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。

如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。

示例 1：

输入：n = "13"
输出："3"
解释：13 的 3 进制是 111。

示例 2：

输入：n = "4681"
输出："8"
解释：4681 的 8 进制是 11111。

示例 3：

输入：n = "1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

提示：

n 的取值范围是 [3, 10¹⁸]
n 没有前导 0

lightbulb

解题思路

方法一：数学

假设 $n$ 在 $k$ 进制下的所有位数均为 $1$ ，且位数为 $m+1$ ，那么有式子 ①：

n=k^0+k^1+k^2+...+k^m

当 $m=0$ 时，上式 $n=1$ ，而题目 $n$ 取值范围为 $[3, 10^{18}]$ ，因此 $m>0$ 。

当 $m=1$ 时，上式 $n=k^0+k^1=1+k$ ，即 $k=n-1>=2$ 。

我们来证明一般情况下的两个结论，以帮助解决本题。

结论一： $m<\log _{k} n$

注意到式子 ① 是个首项为 $1$ ，且公比为 $k$ 的等比数列。利用等比数列求和公式，我们可以得出：

n=\frac{1-k^{m+1}}{1-k}

变形得：

k^{m+1}=k \times n-n+1 < k \times n

移项得：

m<\log _{k} n

题目 $n$ 取值范围为 $[3, 10^{18}]$ ，又因为 $k>=2$ ，因此 $m<\log _{k} n<\log _{2} 10^{18}<60$ 。

结论二： $k=\left \lfloor \sqrt[m]{n} \right \rfloor$

n=k^0+k^1+k^2+...+k^m>k^m

根据二项式定理：

(a+b)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) a^{n-k} b^{k}

整合，可得：

(k+1)^{m}=\left(\begin{array}{c} m \\ 0 \end{array}\right) k^{0}+\left(\begin{array}{c} m \\ 1 \end{array}\right) k^{1}+\left(\begin{array}{c} m \\ 2 \end{array}\right) k^{2}+\cdots+\left(\begin{array}{c} m \\ m \end{array}\right) k^{m}

当 $m>1$ 时，满足：

\forall i \in[1, m-1],\left(\begin{array}{c} m \\ i \end{array}\right)>1

所以有：

\begin{aligned} (k+1)^{m} &=\left(\begin{array}{c} m \\ 0 \end{array}\right) k^{0}+\left(\begin{array}{c} m \\ 1 \end{array}\right) k^{1}+\left(\begin{array}{c} m \\ 2 \end{array}\right) k^{2}+\cdots+\left(\begin{array}{c} m \\ m \end{array}\right) k^{m} \\ &>k^{0}+k^{1}+k^{2}+\cdots+k^{m}=n \end{aligned}

即：

k < \sqrt[m]{n} < k+1

由于 $k$ 是整数，因此 $k=\left \lfloor \sqrt[m]{n} \right \rfloor$ 。

综上，依据结论一，我们知道 $m$ 的取值范围为 $[1,log_{k}n)$ ，且 $m=1$ 时必然有解。随着 $m$ 的增大，进制 $k$ 不断减小。所以我们只需要从大到小检查每一个 $m$ 可能的取值，利用结论二快速算出对应的 $k$ 值，然后校验计算出的 $k$ 值是否有效即可。如果 $k$ 值有效，我们即可返回结果。

时间复杂度 $O(log^{2}n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        def cal(k, m):
            p = s = 1
            for i in range(m):
                p *= k
                s += p
            return s

        num = int(n)
        for m in range(63, 1, -1):
            l, r = 2, num - 1
            while l < r:
                mid = (l + r) >> 1
                if cal(mid, m) >= num:
                    r = mid
                else:
                    l = mid + 1
            if cal(l, m) == num:
                return str(l)
        return str(num - 1)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of mathematical relationships between number representations in different bases.
question_mark
Ensure the candidate can explain why binary search is applied and how it reduces the problem's complexity.
question_mark
Gauge how well the candidate can handle large inputs and optimize the solution for efficiency.

warning

常见陷阱

外企场景

error
Confusing the problem with simpler base conversion problems, missing the requirement for all digits to be 1.
error
Improperly implementing the binary search, such as not properly narrowing the search range for k.
error
Misunderstanding the relationship between n and k, leading to incorrect base calculations or premature exits in the search process.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Given a range of values for n, find the smallest good base for each value using the same binary search method.
arrow_right_alt
Extend the problem to return the base k for multiple values of n in sequence while maintaining efficiency.
arrow_right_alt
Consider a problem where the base k must be larger than a specific value, adding an extra constraint to the search.

help

常见问题

外企场景

继续练习

#497 非重叠矩形中的随机点 #441 排列硬币 #528 按权重随机选择