You are given a string s consisting of digits 0–9 and of length at least two. Further, you are given an integer M. Find the smallest base b such that the string s when interpreted in base-b exceeds M.

For example, if s = 12 and M = 34, then b = 33 because 33 + 2 = 35 > M and 32 + 2 = 34 <= M.

We can solve this problem is O(|S| * log M) time by binary searching on the base. This is because checking if number > M takes O(|S|) time (by going through the characters of the string) and binary search takes O(log M) time.

My question is how to solve this problem in O(|S| + log M) time. I am thinking of checking the binary search in O(1) amortized – which would give the desired result. But, I can’t think of how this optimization could be done. Perhaps we could store the value in a base and use it to compute other bases? Any help would be appreciated.