# LeetCode 483: Smallest Good Base

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!

### 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;
}
};



# Don't use 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(""));
...
};


# Avoid unnecessary one-use temporaries

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

## Related Questions

1  Asked on October 27, 2021 by viktor-v

### Knuth Morris Pratt substring search algorithm

0  Asked on October 27, 2021 by gil-fernandes

### XMLGregorianCalendar to LocalDateTime

1  Asked on October 27, 2021 by mrsmith42

### Multiplying numpy arrays

2  Asked on October 27, 2021 by galacticponderer

### Sum of integers in an interval

6  Asked on October 27, 2021 by james-ross

### First-time F#: A simple Rock Paper Scissors

1  Asked on October 27, 2021 by cimnine

### C++ : Red-Black Tree with std::unique_ptr

1  Asked on October 27, 2021 by frozenca

### Checking if an integer is a palindrome using either a string or a dict

6  Asked on October 27, 2021

### get-release npm module

1  Asked on October 27, 2021 by khushraj-rathod

### Sending a CSV file for a client list from a database

1  Asked on October 27, 2021 by escarta

### A proxy replacement for getters and setters

2  Asked on October 27, 2021

### Checking String with is_numeric in C

2  Asked on October 27, 2021 by ndogac

### Use case of nesting an enum into a struct

2  Asked on October 27, 2021 by matthias-burger

### I have a input grid with more than 40 input-fields hardcoded

1  Asked on October 27, 2021 by darjusch

### Is there a better way to avoid repeated ‘Len == 1’ when interpreting booleans from strings?

1  Asked on October 27, 2021 by user227432

### Reload configs in memory basis on a trigger efficiently

1  Asked on October 27, 2021 by dragons

### Swift Struct-based Factory Pattern

0  Asked on October 27, 2021

### Memoizing a tree’s parent pointers in Python

1  Asked on October 27, 2021 by mark-karavan

### College Billing System – Java

2  Asked on October 27, 2021 by ashwin2125

### Creating a Chart Worksheet from scratch with VBA / OOP Design

1  Asked on October 27, 2021 by jose-cortez