# How to reduce the search space for the base?

• I used to get timeout all the time. I just did linear search for the base from 2 up.

• This post is deleted!

• Hey ,
I have written an editorial , reply if you have doubt
https://discuss.leetcode.com/topic/76332/accepted-solution-in-python

• think about it in a different way, don't search the base up, since the example has given you 9999999999999999, it must timeout. Try to think about how many 1s to represent n using each base. Then you can get something like this

``````floor(log(n, 2))
``````

Since the biggest n is 10^18 and base 2 has the longest 1s, which is about 60.

Just binary search it and verify.

Hope it helps

• @zhongyuan9817 can you exactly explain what is that supposed to mean ? For instance I have to search for n = 10x10^18, so the largest 1s are of 2 which are 60. So, what exactly are you suggesting from binary search, can you elaborate a bit more.

On what matrices we have to use binary search, you can provide with a testcase just for a simple number for instance 10 or 100 or 1000.

• It can be mathematically proved that

• the upper bound for number of digits `d``log`2`(N+1)`.

And then the good base `k` will be uniquely determined by `d`.

By the way, the search of `k` should always go by `d` from upper bound down because the larger the `d`, the smaller the `k`.

I have a post here if you are interested:
10-liner 3ms really TIGHT search bounds with time complexity analysis O((logN)^2) (detailed explanation)

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