TransWikia.com

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

References

algorithmbeginnerc++c++17programming challenge

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

Recent Questions

Recent Answers

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