If \(X\)’s length is \(1\), then the answer is \(0\) or \(1\). Let us consider otherwise.

Let \(f(n)\) be the value of \(X\) interpreted base \(n\), then \(f\) is strictly monotonically increasing. Therefore, one can find the maximum \(n\) such that \(f(n)\leq M\) with binary search, and thus solve the problem.

When \(X\) is 10, the answer can be at most about \(M\). Be careful of overflows in the course of calculation.

Let \(L\) be the length of \(X\), then the time complexity is \(O(L \log M)\). With proper implementation, one can solve it in an \(O(\log M)\) time (plus receiving the input).