0483. Smallest Good Base

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:

  1. The range of n is [3, 10^18].
  2. 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 使得
\[ \sum_{i=0}^{m} k^{i} = \frac{1-k^{m+1}}{1-k} = n\]
  • 这一题需要确定 k 和 m 两个数的值。m 和 k 是有关系的,确定了一个值,另外一个值也确定了。由
\[ \frac{1-k^{m+1}}{1-k} = n \\\]

可得:

\[ m = log_{k}(kn-n+1) - 1 < log_{k}(kn) = 1 + log_{k}n\]

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

\[ 1 \leqslant m \leqslant log_{2}n\]

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

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

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

可得,

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

所以 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)
}



⬅️上一页

下一页➡️

Calendar Jul 16, 2021
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者