Python solution with detailed mathematical explanation and derivation


  • 20
    H

    First things first. Let's see the math behind it.

    From given information, we can say one thing- Numbers will be of form-

    n = k^m + k^(m-1) + ... + k + 1
    => n-1 = k^m + k^(m-1) + ... + k
    => n-1 = k (k^(m-1) + k^(m-2) + ... + k + 1) ...... [1]

    Also, from n = k^m + k^(m-1) + ... + k + 1, we can say,
    n-k^m = k^(m-1) + k^(m-2) + ... + k + 1 ...... [2]

    from [1] and [2],

    n-1 = k (n - k^m)
    =>k^(m+1) = nk - n + 1

    if you shuffle sides you will end up getting following form,

    (k^(m+1) - 1)/(k - 1) = n .... [3]

    Also from [1] note that, (n - 1) must be divisible by k.

    We know that, n = k^m + k^(m-1) + ... + k + 1

    => n > k^m
    => m-th root of n > k .... [4]

    [EDIT] -->

    With inputs from @StefanPochmann we can also say, from binomial thorem, n = k^m + ... + 1 < (k+1)^m .... [5]
    Therefore, k+1 > m-th root of n > k. .... from [4] and [5]
    Thus ⌊m-th root of n⌋ is the only candidate that needs to be tested. [6]

    <--

    So our number should satisfy this equation where k will be our base and m will be (number of 1s - 1)

    This brings us to the search problem where we need to find k and m.

    Linear search from 1 to n does not work. it gives us TLE. So it leaves us with performing some optimization on search space.

    From [6] we know that the only candidate that needs to be tested is, ⌊m-th root of n⌋

    We also know that the smallest base is 2 so we can find our m must be between 2 and log2n else m is (n-1) [7]

    That brings me to the code:
    [EDIT] -- >

    import math
    class Solution(object):
        def smallestGoodBase(self, n):
            """
            :type n: str
            :rtype: str
            """
            n = int(n)
            max_m = int(math.log(n,2)) # Refer [7]
            for m in range(max_m,1,-1):
                k = int(n**m**-1)  # Refer [6]
                if (k**(m+1)-1)//(k-1) == n:
                    # Refer [3]
                    return str(k)
            
            return str(n-1)  
    

    <—-


  • 0

    Nice explanation. Two little mistakes: (not anymore, after the edit)

    • You fail n = "3", returning "1".
    • 10^18 < 2^55 is false. But it doesn't seem to matter?

  • 16

    For a given m > 1:

    From n = km + ... + k0 > km you get k < m-th root of n (as you said already).
    From n = km + ... + k0 < (k+1)m (see binomial theorem) you also get k+1 > m-th root of n.

    So k < m-th root of n < k+1. Thus ⌊m-th root of n⌋ is the only candidate that needs to be tested. As @hausch did here.


    Edit: More explanations:

    I think of the above k < x < k+1 (with x being the m-th root of n) as x being really close to the potentially existing k. Rounding it down might be a working k, but integers larger than that can't be (because already x is larger than k) and integers smaller also can't be (because x < k+1 shows that x is less than 1 too large, so if we subtract 1 or more, we'd be too small).

    You can also reverse the focus, though, and turn those inequations into x-1 < k < x. In other words, k would have to be an integer between x-1 and x. So round down x to get the only integer in that little range. Yeah ok, this is probably the easier viewpoint :-)

    And to show km + ... + k0 < (k+1)m: One way to see it is that expanding (k+1)m gives you all those powers of k, most of them multiple times, for example (k+1)4 = k4+4k3+6k2+4k1+k0. The binomial theorem just makes that more formal, giving us (k+1)m = i=0:m (m choose i)⋅ki. Here (m choose i) is at least 1, and larger than 1 when i is strictly between 0 and m (this is btw where "m > 1" comes into play, guaranteeing such an i). So we have (k+1)m = i=0:m (m choose i)⋅ki > i=0:m ki.


  • 0
    Z

  • -1

    @StefanPochmann nice proof!


  • 0
    H

    @StefanPochmann Thanks for your inputs! I will take that in account.


  • 0

    @harshaneel Did you accidentally remove your derivation of "m-th root of n > k"? I don't see it anymore, but I think I got that part from you.


  • 0
    H

    @StefanPochmann Yeah I accidentally removed it. Added it again with some more comments and references.


  • 0

    @StefanPochmann I had a proof to get a lower bound as (m+1)st root of n in my post. I thought it was tight enough, but... :-(


  • 0
    R

    @StefanPochmann I didn't understand why the floor of m-th root of n has to be the only candidate for k.

    k < m-th root of n < k+1. I can only understand that m-th root of n will be a float because k is always a positive number. Also, won't the floor of m-th root on n be k and not more than it ?

    Sorry if I asked a stupid question


  • 1
    Z

    @rtmatx
    k < m-th root of n < k+1

    2 < x < 3
    x must be 2.xxxxx
    floor(x) just round this float number to the largest previous integer, so it must equal to integer 2, how could it be more than 2?


  • 1

    @rtmatx I added some more explanations, have a look again.


  • 0
    This post is deleted!

  • 0
    R

    @zhongyuan9817 Thanks @zhongyuan9817 I understood the logic. I am not thinking in the correct way!


  • 0
    R

    @StefanPochmann Thanks a lot. Your new explanation cleared all my doubts. I am sorry if it took you lot of time :(


  • 0
    S

    @StefanPochmann
    Can the same logic be written in C++ code ?


  • 0

  • 1
    L

    @StefanPochmann Can you prove that that the smallest base is between 2 and log2n else m is (n-1)?


  • 2
    L

    @livelearn
    We know n > k^m. Since k>=2, we can get m<=log2(n). We know n is an non-negative integer. Here, the input n is between [3, 10^18]. Therefore, m cannot be zero, in which case n=1. When m=1, the base k is (n-1), because (n-1)^1+(n-1)^0=n. Here, (n-1) is always a good base.

    @harshaneel I think you mean "else base k is (n-1) [7]", right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.