如何在O(|S| + log M)时间内找到使字符串s超M的最小基数

核心思路 #

要把时间复杂度从O(|S|logM)优化到O(|S|+logM)，关键是减少高复杂度的检查操作次数，同时利用数学性质缩小二分查找的范围，避免每次都遍历整个字符串计算数值。

具体步骤 #

1. 预处理与基础判断

   • 把字符串s转成数字数组digits，比如s="12"转成[1,2]。
   • 计算基数的最小值b_min：等于字符串中最大数字加1（比如s="12"最大数字是2，b_min=3），因为基数必须大于所有出现的数字。
   • 先计算s在b_min进制下的数值，计算时一旦超过M就立刻停止，直接返回b_min——这一步是O(|S|)时间。如果计算完发现V(b_min) <= M，再进入后续步骤。

2. 缩小二分查找的上界
   字符串长度k=|S|，分两种情况处理：

   • 当k=2时：
     s在b进制下的值是digits[0]*b + digits[1]，要让这个值大于M，解不等式得b > (M - digits[1])/digits[0]，所以候选上界b_upper = max(b_min, floor((M - digits[1])/digits[0]) + 1)，直接计算即可，不用二分。
   • 当k>2时：
     s在b进制下的值V(b) >= b^(k-1)（因为最高位至少是1），当b > M^(1/(k-1))时，b^(k-1) > M，必然满足V(b) > M。用牛顿迭代法快速计算b_upper = floor(M^(1/(k-1))) + 1，这个迭代过程是O(log log M)时间，属于O(log M)范畴。

3. 二分查找最小基数
   在区间[b_min, b_upper]内做二分查找，每次检查V(b)是否大于M时，边计算边判断溢出/超过M：

   def is_greater(b):
       val = 0
       for d in digits:
           val = val * b + d
           if val > M:
               return True
       return val > M
   

   当b较大时，计算到前几位就会超过M，直接返回True，无需遍历整个字符串；只有b较小时才需要完整计算。由于b_upper的范围被大幅缩小，二分查找的次数是O(log M)级别，且总检查操作的时间复杂度是O(|S| + log M)。

例子验证 #

比如s="12"，M=34：

• 预处理得digits=[1,2]，b_min=3，计算V(3)=1*3+2=5<=34。
• k=2，计算b_upper = max(3, floor((34-2)/1)+1)=max(3,32+1)=33。
• 二分查找确认b=33时，1*33+2=35>34，而b=32时1*32+2=34<=34，所以返回33，符合预期。

内容的提问来源于stack exchange，提问作者MangoPizza