I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!
Problem
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.
Inputs
"1000000000000000000"
"999999999999999999"
"141038407950127511"
"836507047502348570"
"123489798271512411"
"995437985793784539"
"4681"
"4800"
"48000"
"480000"
"5120000"
"51200000"
Outputs
"999999999999999999"
"999999999999999998"
"141038407950127510"
"836507047502348569"
"123489798271512410"
"995437985793784538"
"8"
"4799"
"47999"
"479999"
"5119999"
"51199999"
Code
#include <cstdint>
#include <string>
#include <algorithm>
struct Solution {
std::string smallestGoodBase(const std::string n) {
std::uint_fast64_t num = (std::uint_fast64_t) std::stoull(n);
std::uint_fast64_t x = 1;
for (int bit = 62; bit > 0; --bit) {
if ((x << bit) < num) {
std::uint_fast64_t curr = binarySearch(num, bit);
if (curr) {
return std::to_string(curr);
}
}
}
return std::to_string(num - 1);
}
private:
static std::uint_fast64_t binarySearch(
const std::uint_fast64_t num,
const
std::uint_fast8_t bit
) {
const long double dnum = (long double) num;
std::uint_fast64_t lo = 1;
std::uint_fast64_t hi = (std::uint_fast64_t) (std::pow(dnum, 1.0 / bit) + 1);
while (lo < hi) {
std::uint_fast64_t mid = lo + ((hi - lo) >> 1);
std::uint_fast64_t sum = 1;
std::uint_fast64_t curr = 1;
for (std::uint_fast8_t iter = 1; iter <= bit; ++iter) {
curr *= mid;
sum += curr;
}
if (sum == num) {
return mid;
} else if (sum > num) {
hi = mid;
} else {
lo = mid + 1;
}
}
return 0;
}
};