I have written an editorial , reply if you have doubt
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
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
And then the good base
k will be uniquely determined by
By the way, the search of
k should always go by
d from upper bound down because the larger the
d, the smaller the
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.