In this guide, you will get 483. Smallest Good Base LeetCode Solution with the best time and space complexity. The solution to Smallest Good Base problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Constraints:
n is an integer in the range [3, 1018].
n does not contain any leading zeros.
Complexity Analysis
Time Complexity: O(\log^2n)
Space Complexity: O(1)
483. Smallest Good Base LeetCode Solution in C++
class Solution {
public:
string smallestGoodBase(string n) {
const long num = stol(n);
for (int m = log2(num); m >= 2; --m) {
const int k = pow(num, 1.0 / m);
long sum = 1;
long prod = 1;
for (int i = 0; i < m; ++i) {
prod *= k;
sum += prod;
}
if (sum == num)
return to_string(k);
}
return to_string(num - 1);
}
}; /* code provided by PROGIEZ */
483. Smallest Good Base LeetCode Solution in Java
class Solution {
public String smallestGoodBase(String n) {
final long num = Long.parseLong(n);
final int log2 = (int) (Math.log(num) / Math.log(2));
for (int m = log2; m >= 2; --m) {
int k = (int) Math.floor(Math.pow(num, 1.0 / m));
long sum = 1;
long prod = 1;
for (int i = 0; i < m; ++i) {
prod *= k;
sum += prod;
}
if (sum == num)
return String.valueOf(k);
}
return String.valueOf(num - 1);
}
} // code provided by PROGIEZ
483. Smallest Good Base LeetCode Solution in Python
class Solution:
def smallestGoodBase(self, n: str) -> str:
n = int(n)
for m in range(int(math.log(n, 2)), 1, -1):
k = int(n**m**-1)
if (k**(m + 1) - 1) // (k - 1) == n:
return str(k)
return str(n - 1) # code by PROGIEZ
