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:

- These types are actually different from the regular
`std::uint*_t`

- Implicit casts and integer promotions don't change the actual type used

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

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP