Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/483.html
483. Smallest Good Base (Hard)
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:
- The range of n is [3, 10^18].
- The string representing n is always valid and will not have leading zeros.
Related Topics:
Math, Binary Search
Solution 1.
n - 1 is the greatest good base since n base(n-1) = 11.
Assume x is the next smaller good base, then n base(x) = 111 or x^2 + x + 1 = n. x = sqrt(n - x - 1) < sqrt(n).
Let k = sqrt(n) and assume val base(k) = 111. val should be greater than n.
Then we keep decrement k to approach x, and the val which satisfies val base(k) = 111 approaches n as well.
We keep decrementing k until val <= num.
If val == n, we find a good base k; otherwise (val < n), k is not a good base.
We continue to look for the next smaller good base y, then n base(y) = 1111 or y^3 + y^2 + y + 1 = n. y = cbrt(n - y^2 - y - 1) < cbrt(n).
So we can do similar approach as above, let k = cbrt(n) and try to approach y.
As we keep looking for the next good base z, we start from k = pow(n, 1 / (cnt - 1)) where cnt is the number of ones in n base(z).
We stop the process once k < 2. The last good base we found is the answer.
// OJ: https://leetcode.com/problems/smallest-good-base/
// Time: O(logN)
// Space: O(1)
typedef unsigned long long ULL;
class Solution {
private:
ULL getValue(ULL base, int cnt) {
ULL ans = 1, p = 1;
while (--cnt) ans += (p *= base);
return ans;
}
public:
string smallestGoodBase(string n) {
ULL num = stoull(n), ans = num - 1, cnt = 3, k, val;
while (true) {
k = pow(num, 1 / (double)(cnt - 1));
if (k < 2) break;
do {
val = getValue(k, cnt);
if (val == num) ans = k;
--k;
} while (val > num);
++cnt;
}
return to_string(ans);
}
};
Solution 2.
// OJ: https://leetcode.com/problems/smallest-good-base/
// Time: O(logN)
// Space: O(1)
// Ref: https://leetcode.com/problems/smallest-good-base/discuss/96590/3ms-AC-C++-long-long-int-+-binary-search/101166
class Solution {
typedef unsigned long long ull;
public:
string smallestGoodBase(string n) {
ull num = (ull)stoll(n);
int maxlen = log(num) / log(2) + 1;
for(int k = maxlen; k >= 3; --k){
ull b = pow(num, 1.0 / (k - 1)), sum = 1, cur = 1;
for (int i = 1; i < k; ++i) sum += (cur *= b);
if (sum == num) return to_string(b);
}
return to_string(num - 1);
}
};
-
class Solution { public String smallestGoodBase(String n) { long num = Long.parseLong(n); long max = (long) (Math.log(num) / Math.log(2)); for (long i = max; i > 1; i--) { long base = (long) Math.pow(num, 1.0 / i); long sum = 0; for (long j = 0; j <= i; j++) sum = sum * base + 1; if (sum == num) return String.valueOf(base); } return String.valueOf(num - 1); } } ############ class Solution { public String smallestGoodBase(String n) { long num = Long.parseLong(n); for (int len = 63; len >= 2; --len) { long radix = getRadix(len, num); if (radix != -1) { return String.valueOf(radix); } } return String.valueOf(num - 1); } private long getRadix(int len, long num) { long l = 2, r = num - 1; while (l < r) { long mid = l + r >>> 1; if (calc(mid, len) >= num) r = mid; else l = mid + 1; } return calc(r, len) == num ? r : -1; } private long calc(long radix, int len) { long p = 1; long sum = 0; for (int i = 0; i < len; ++i) { if (Long.MAX_VALUE - sum < p) { return Long.MAX_VALUE; } sum += p; if (Long.MAX_VALUE / p < radix) { p = Long.MAX_VALUE; } else { p *= radix; } } return sum; } } -
// OJ: https://leetcode.com/problems/smallest-good-base/ // Time: O(logN) // Space: O(1) typedef unsigned long long ULL; class Solution { private: ULL getValue(ULL base, int cnt) { ULL ans = 1, p = 1; while (--cnt) ans += (p *= base); return ans; } public: string smallestGoodBase(string n) { ULL num = stoull(n), ans = num - 1, cnt = 3, k, val; while (true) { k = pow(num, 1 / (double)(cnt - 1)); if (k < 2) break; do { val = getValue(k, cnt); if (val == num) ans = k; --k; } while (val > num); ++cnt; } return to_string(ans); } }; -
class Solution: def smallestGoodBase(self, n: str) -> str: def cal(k, m): p = s = 1 for i in range(m): p *= k s += p return s num = int(n) for m in range(63, 1, -1): l, r = 2, num - 1 while l < r: mid = (l + r) >> 1 if cal(mid, m) >= num: r = mid else: l = mid + 1 if cal(l, m) == num: return str(l) return str(num - 1) ############ import math class Solution(object): def smallestGoodBase(self, n): """ :type n: str :rtype: str """ n = int(n) max_m = int(math.log(n, 2)) # Refer [7] for m in range(max_m, 1, -1): k = int(n ** m ** -1) if (k ** (m + 1) - 1) / (k - 1) == n: return str(k) return str(n - 1)