# 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 = 1 + k + k^2 + k^3 + … + k^(m-1)

n = 1 + k + k^2 + k^3 + … + k^(m-1) > k^(m-1)

``````class Solution {
public:
string smallestGoodBase(string n) {
long long num = stol(n);
for (int i = log(num + 1) / log(2); i >= 2; --i) {
long long left = 2, right = pow(num, 1.0 / (i - 1)) + 1;
while (left < right) {
long long mid = left + (right - left) / 2, sum = 0;
for (int j = 0; j < i; ++j) {
sum = sum * mid + 1;
}
if (sum < num) left = mid + 1;
else right = mid;
}
}
}
};
``````

Github 同步地址：

https://leetcode.com/problems/smallest-good-base/

https://leetcode.com/problems/smallest-good-base/discuss/96591/Java-O((logn)2)-binary-search-solution

https://leetcode.com/problems/smallest-good-base/discuss/96593/Concise-C%2B%2B-Binary-Search-solution

https://leetcode.com/problems/smallest-good-base/discuss/96590/3ms-AC-C%2B%2B-long-long-int-%2B-binary-search

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation