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 的取值范围是 [3, 10^18]。
• 输入总是有效且没有前导 0。

## 解题思路 #

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

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

## 代码 #

``````
package leetcode

import (
"math"
"strconv"
)

func smallestGoodBase(n string) string {
num, _ := strconv.ParseUint(n, 10, 64)
for bit := uint64(math.Log2(float64(num))); bit >= 1; bit-- {
low, high := uint64(2), uint64(math.Pow(float64(num), 1.0/float64(bit)))
for low < high {
mid := uint64(low + (high-low)>>1)
sum := findBase(mid, bit)
if sum == num {
return strconv.FormatUint(mid, 10)
} else if sum > num {
high = mid - 1
} else {
low = mid + 1
}
}
}
return strconv.FormatUint(num-1, 10)
}

// 计算 k^m + k^(m-1) + ... + k + 1
func findBase(mid, bit uint64) uint64 {
sum, base := uint64(1), uint64(1)
for i := uint64(1); i <= bit; i++ {
base *= mid
sum += base
}
return sum
}

``````

Sep 6, 2020
Edit this page