Last updated on March 1st, 2025 at 10:01 pm
Here, we see the Smallest Good Base LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Binary Search, Math
Companies
Level of Question
Hard
Smallest Good Base LeetCode Solution
Table of Contents
1. Problem Statement
Given an integer n represented as a string, return the smallest good base of n.
We call k >= 2 a good base of n, if all digits of n base k are 1‘s.
Example 1:
Input: n = “13”
Output: “3”
Explanation: 13 base 3 is 111.
Example 2:
Input: n = “4681”
Output: “8”
Explanation: 4681 base 8 is 11111.
Example 3:
Input: n = “1000000000000000000”
Output: “999999999999999999”
Explanation: 1000000000000000000 base 999999999999999999 is 11.
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Modified Binary Search. The problem involves finding the smallest good base for a given number n, and the solution uses binary search to efficiently determine the base that satisfies the condition. The binary search is applied to the range of possible bases, and for each base, the sum of the geometric series is calculated to check if it equals n.
3. Code Implementation in Different Languages
3.1 Smallest Good Base C++
class Solution {
public:
string smallestGoodBase(string n) {
typedef unsigned long long ll;
ll num = stol(n);
for (ll p = log(num+1) / log(2); p >= 2; --p) {
ll lk = 2, rk = pow(num, 1.0 / (p-1))+1;
while (lk <= rk) {
ll mk = lk + (rk - lk) / 2, sum = 0;
for (ll i = 0, f = 1; i < p; ++i, f *= mk)
sum += f;
if (sum < num) lk = mk+1;
else if (sum > num) rk = mk-1;
else return to_string(mk);
}
}
return to_string(num-1);
}
};
3.2 Smallest Good Base Java
class Solution {
public String smallestGoodBase(String n) {
long tn = Long.parseLong(n);
long x = 1;
for (int i = 62; i >= 1; i--) {
if ((x << i) < tn) {
long cur = mySolve(tn, i);
if (cur != 0) {
return Long.toString(cur);
}
}
}
return Long.toString(tn - 1);
}
private long mySolve(long n, int d) {
double tn = (double) n;
long right = (long) (Math.pow(tn, 1.0 / d) + 1);
long left = 1;
while (left <= right) {
long mid = left + (right - left) / 2;
long sum = 1, cur = 1;
for (int i = 1; i <= d; i++) {
cur *= mid;
sum += cur;
}
if (sum == n) {
return mid;
}
if (sum > n) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return 0;
}
}
3.3 Smallest Good Base JavaScript
var smallestGoodBase = function (n) {
n = BigInt(n);
let compute = (base, len) => (base ** BigInt(len) - 1n) / (base - 1n);
for (let len = BigInt(Math.floor(Math.log2(Number(n))) + 1); len >= 2n; len--) {
let low = 2n, high = n;
while (low <= high) {
let mid = (low + high) / 2n;
let sum = compute(mid, len);
if (sum === n) {
return mid.toString();
} else if (sum < n) {
low = mid + 1n;
} else {
high = mid - 1n;
}
}
}
return (n - 1n).toString();
};
3.4 Smallest Good Base Python
class Solution(object):
def smallestGoodBase(self, n):
s=1
ans = []
n = int(n)
while(s<65):
l=2
h=10**18
res = -1
while(l<=h):
mid=(l+h)//2
p = (mid**s - 1)//(mid-1)
if p == n:
res = mid
h = mid - 1
else:
if p>n:
h = mid - 1
else:
l = mid + 1
if res!=-1:
ans.append(res)
s+=1
return str(min(ans))
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(log(n) * log(n) * m) | O(1) |
| Java | O(log(n) * log(n) * m) | O(1) |
| JavaScript | O(log(n) * log(n) * m) | O(1) |
| Python | O(log(n) * log(n) * m) | O(1) |
where, n is the given number and m is the length of the series.
- The algorithm is efficient because it leverages the logarithmic nature of the problem and uses binary search to minimize the number of computations.
- The geometric series calculation is optimized to avoid overflow by using iterative multiplication or direct formulas.
- The solution is implemented in a language-agnostic way, with minor differences in syntax and data type handling across C++, Java, JavaScript, and Python.