483. Smallest Good Base

题目

For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.

Now given a string representing n, you should return the smallest good base of n in string format.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

The range of n is [3, 10^18].
The string representing n is always valid and will not have leading zeros.

题目大意

对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。

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

提示：

n 的取值范围是 [3, 10^18]。
输入总是有效且没有前导 0。

解题思路

给出一个数 n，要求找一个进制 k，使得数字 n 在 k 进制下每一位都是 1 。求最小的进制 k。
这一题等价于求最小的正整数 k，满足存在一个正整数 m 使得

{{< katex display >}} \sum_{i=0}^{m} k^{i} = \frac{1-k^{m+1}}{1-k} = n {{< /katex >}}

这一题需要确定 k 和 m 两个数的值。m 和 k 是有关系的，确定了一个值，另外一个值也确定了。由

{{< katex display >}} \frac{1-k^{m+1}}{1-k} = n \ {{< /katex >}}

可得：

{{< katex display >}} m = log_{k}(kn-n+1) - 1 < log_{k}(kn) = 1 + log_{k}n {{< /katex >}}

根据题意，可以知道 k ≥2，m ≥1 ，所以有:

{{< katex display >}} 1 \leqslant m \leqslant log_{2}n {{< /katex >}}

所以 m 的取值范围确定了。那么外层循环从 1 到 log n 遍历。找到一个最小的 k ，能满足：

可以用二分搜索来逼近找到最小的 k。先找到 k 的取值范围。由

{{< katex display >}} \frac{1-k^{m+1}}{1-k} = n \ {{< /katex >}}

可得，

{{< katex display >}} k^{m+1} = nk-n+1 < nk\ \Rightarrow k < \sqrt[m]{n} {{< /katex >}}

所以 k 的取值范围是 [2, n*(1/m) ]。再利用二分搜索逼近找到最小的 k 即为答案。

代码


package leetcode

import (
	"math"
	"math/bits"
	"strconv"
)

func smallestGoodBase(n string) string {
	nVal, _ := strconv.Atoi(n)
	mMax := bits.Len(uint(nVal)) - 1
	for m := mMax; m > 1; m-- {
		k := int(math.Pow(float64(nVal), 1/float64(m)))
		mul, sum := 1, 1
		for i := 0; i < m; i++ {
			mul *= k
			sum += mul
		}
		if sum == nVal {
			return strconv.Itoa(k)
		}
	}
	return strconv.Itoa(nVal - 1)
}