Code Review Asked on January 2, 2022
I’m posting my code for a LeetCode problem. If you’d like to review, please do so. Thank you for your time!
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.
"1000000000000000000"
"999999999999999999"
"141038407950127511"
"836507047502348570"
"123489798271512411"
"995437985793784539"
"4681"
"4800"
"48000"
"480000"
"5120000"
"51200000"
"999999999999999999"
"999999999999999998"
"141038407950127510"
"836507047502348569"
"123489798271512410"
"995437985793784538"
"8"
"4799"
"47999"
"479999"
"5119999"
"51199999"
#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;
}
};
std::uint_fast*_t
The performance gain of these types is minimal. If you really need to squeeze out the last bits of performance, it might help, but only if:
std::uint*_t
The drawback is that the type names get very verbose. Also, can a std::uint_fast64_t
actually hold an unsigned long long
? The latter might very well be 128 bits long.
I suggest you stick with (unsigned
) int
when dealing with numbers that don't grow large (for example, for counting bits), size_t
when you need to support arbitratily large counts, sizes and array indices, and other types as appropriate, such as unsigned long long
to store the results of std::stoull()
.
Also use a using
declaration to declare the type used to store the numbers in one place, so if you ever decide to change it, you don't have to search and replace all over the code. You can combine it with decltype()
to get the type returned by an arbitrary function, like so:
class Solution {
using value_type = decltype(std::stoull(""));
...
};
There are several cases where you define a temporary variable that is only used once, and which could be avoided. The first is x
, which is only used to create a constant 1
of the right type. You can do that instead like so:
if ((value_type{1} << bit) < num) {
...
}
The second one will still technically create a temporary, but we can use C++17's if
with an init statement:
if (auto curr = binarySearch(num, bit); curr) {
return curr;
}
When passing an integer type to std::pow()
, it will convert it to double
for you, so you don't have to explcitly create a temporary constant dnum
, and can just write:
value_type hi = std::pow(num, 1.0 / bit) + 1;
Note that you also don't need to explicitly cast it back to an integer here.
Answered by G. Sliepen on January 2, 2022
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP