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 使得

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

可得:

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

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

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

可得,

所以 k 的取值范围是 [2, n*(1/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
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者