class Solution {
public:
string smallestGoodBase(string n) {
}
};
483. 最小好进制
以字符串的形式给出 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, 1018]n 没有前导 0原站题解
rust 解法, 执行用时: 12 ms, 内存消耗: 2.2 MB, 提交时间: 2023-09-14 15:26:06
impl Solution {
pub fn smallest_good_base(n: String) -> String {
let num = n.parse::<u128>().unwrap();
let mut ans = u128::MAX;
for i in 1..64 {
let mut lo = 2;
let mut hi = num;
while lo <= hi && hi <= num {
let mid = lo + (hi - lo) / 2;
let mut tmp = 0;
for j in 0..=i {
tmp = tmp * mid + 1;
}
if tmp == num {
ans = mid;
break;
}
if tmp < num {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
ans.to_string()
}
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16 MB, 提交时间: 2023-09-14 15:25:18
class Solution:
def smallestGoodBase(self, n: str) -> str:
num = int(n)
for m in range(num.bit_length(),2,-1):
x = int(pow(num,1/(m-1)))
if num == (pow(x,m) - 1)//(x-1):
return str(x)
return str(num-1)
python3 解法, 执行用时: 56 ms, 内存消耗: 15.8 MB, 提交时间: 2023-09-14 15:25:00
class Solution:
def smallestGoodBase(self, n: str) -> str:
import math
max_p = int(math.log(int(n),2)) # 如果用for循环对幂次p从1开始到n，肯定超时。这里能想到。
for p in range(max_p,0,-1):
k = int(pow(int(n),1.0/p)) # 对k的范围确定，如果同样从1开始到n，肯定超时，这里想不到。
#value = (pow(k,p+1)-1)/(k-1) # 如果用等比数列求和公式，肯定造成溢出，导致错误。
#### 下面是计算等比数列求和
sum_value = 1
mul = 1
for i in range(1,p+1): # 等比数列求和
mul*=k
sum_value+=mul
# 如果求和结果等于n，则直接返回str(k)
if sum_value==int(n):
return str(k)
# 如果不满足上述要求，直接返回最大的k: 即 n-1
return str(int(n)-1)
golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-14 15:23:11
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)
}
javascript 解法, 执行用时: 80 ms, 内存消耗: 43.9 MB, 提交时间: 2023-09-14 15:22:55
/**
* @param {string} n
* @return {string}
*/
var smallestGoodBase = function(n) {
const nVal = parseInt(n);
const mMax = Math.floor(Math.log(nVal) / Math.log(2));
for (let m = mMax; m > 1; m--) {
const k = BigInt(Math.floor(Math.pow(nVal, 1.0 / m)));
if (k > 1) {
let mul = BigInt(1), sum = BigInt(1);
for (let i = 1; i <= m; i++) {
mul *= k;
sum += mul;
}
if (sum === BigInt(n)) {
return k + '';
}
}
}
return (BigInt(n) - BigInt(1)) + '';
};
java 解法, 执行用时: 2 ms, 内存消耗: 39.7 MB, 提交时间: 2023-09-14 15:22:39
class Solution {
public String smallestGoodBase(String n) {
long nVal = Long.parseLong(n);
int mMax = (int) Math.floor(Math.log(nVal) / Math.log(2));
for (int m = mMax; m > 1; m--) {
int k = (int) Math.pow(nVal, 1.0 / m);
long mul = 1, sum = 1;
for (int i = 0; i < m; i++) {
mul *= k;
sum += mul;
}
if (sum == nVal) {
return Integer.toString(k);
}
}
return Long.toString(nVal - 1);
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-14 15:22:23
class Solution {
public:
string smallestGoodBase(string n) {
long nVal = stol(n);
int mMax = floor(log(nVal) / log(2));
for (int m = mMax; m > 1; m--) {
int k = pow(nVal, 1.0 / m);
long mul = 1, sum = 1;
for (int i = 0; i < m; i++) {
mul *= k;
sum += mul;
}
if (sum == nVal) {
return to_string(k);
}
}
return to_string(nVal - 1);
}
};