Base N numbers

As we know, we are using different base numbers in our life. Decimal is base 10. Month, base 12. Computers are base 2.

For computers, we also have base 16, base 8 …

For the base N number, generally speaking, it means we can have N choices for each digit of this base number. Then by using the multiplication principle, we can easily figure out that we total can represent:

N^n different numbers where N is the base, n is the number of digits that we can use.

Several questions are related to base N numbers in Leetcode. I’d like to have a quick summary to help readers to go through these questions and have a good feeling when encountering this kind of problem.

483. Smallest Good Base

Smallest Good Base - LeetCode

This is a hard interview question from google. It seems that google prefers some hard related to math and computer fundamental questions. I can not solve this problem if it is the first time I see this question.

A naive way will check from base 2 to base INF until we find the first base K which can satisfy the requirement.

However, when I see this test case, I gave up as it definitely will get TLE.

Input: "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

Here is the code related to this TLE idea

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        k, n = 2, int(n)
        def good(k):
            # if 1+k+k**2+k**m ==n
            # what is m?
            # (k**(m+1)-1)/(k-1)==n
            # k**(m+1) = n*(k-1)+1
            # m= math.log(n*(k-1)+1, k)-1
            m= math.log(n*(k-1)+1, k) -1
            if k==362:print(m)
            #print(k, m)
            return m==int(m)
            
        while True:
            if good(k):return str(k)
            k += 1
50 / 106 test cases passed.

We get a WA when n = “131407”

Input:              "131407"
Output:              "131406"
Expected:              "362"

If we print out the result when k == 362, we get m=1.9999999999999996

It seems that the math.log result will get some error.

We can figure it out by compare the absolute error with a small value. This time we get TLE as expected.

55 / 106 test cases passed.
Status:

Time Limit Exceeded

Submitted: 0 minutes ago

Last executed input: "470988884881403701"

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        k, n = 2, int(n)
        def good(k):
            # if 1+k+k**2+k**m ==n
            # what is m?
            # (k**(m+1)-1)/(k-1)==n
            # k**(m+1) = n*(k-1)+1
            # m= math.log(n*(k-1)+1, k)-1
            m= math.log(n*(k-1)+1, k) -1
            #if k==362:print(m)
            #print(k, m)
            return abs(m-round(m))<=1e-10
            
        while True:
            if good(k):return str(k)
            k += 1

What about using a binary search?

This beautiful handwriting analysis saved my day.

Reference of this image is:

https://leetcode.com/problems/smallest-good-base/discuss/96589/Java-solution-with-hand-writing-explain

It is easy to see that n-1 can always be good as 1*(n-1)¹+1*(n-1)⁰=n

so k should be the smallest good value from [2, n-1].

By using the beautiful handwriting image, we can have the code based on binary search.

Python code is here and the complexity is O(60*log(n)) which is O(log(n))

we can begin from 59 as
math.log(10**18, 2) = 59.794705707972525
The reason to begin from the longest to shortest is the longest will have the smallest base number.

The critical part to solve this problem is the equation shown in the picture. This is essentially how to calculate the sum of the geometric sequence.

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        n = int(n)
        
        for length in range(59, 1, -1):
            l, r = 2, n-1
            while l<=r:
                m = (l+r)//2
                # https://leetcode.com/problems/smallest-good-base/discuss/96589/Java-solution-with-hand-writing-explain
                left, right =  n*(m-1), m**length-1
                if left==right:return str(m)
                elif left<right:# m is too large
                    r = m-1
                else:# m is too small
                    l = m + 1

run time of above code

Runtime: 468 ms, faster than 5.56% of Python3 online submissions for Smallest Good Base.
Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Smallest Good Base.