是否存在一种算法可以在恒定时间内将一个（以 10 为底的）数字转换为另一个任意基数的数字？

Question

我正在解决给定 three integers (a,b,c)、这三个问题都可能非常大 和 (a>b>c)

我想确定 b 和 c 之间的哪个基数，产生 最小的数字总和 ，当我们转换 'a' 到那个基地。

例如a = 216, b=2, c=7 -> the output= 6，因为：216 base 2 = 11011000，和sum of digits = 4，如果我们对all bases between 2 and 7做同样的事情，我们发现216 base 6 产生最小的数字总和 ，因为 216 base 6 = 1000 的总和为 1.

我的问题是，是否有任何函数可以比以下算法更快地在恒定时间内将数字转换为任何基数？或者对如何优化我的算法有什么建议吗？

from collections import defaultdict
n = int(input())
for _ in range(n):
    (N,X) = map(int,input().split())
    array = list(map(int,input().split()))
    my_dict = defaultdict(int)

    #original count of elements in array
    for i in range(len(array)):
        my_dict[array[i]] +=1

    #ensure array contains distinct elements
    array = set(array)
    count = max(my_dict.values())  #count= max of single value
    temp = count
    res = None
    XOR_count = float("inf")
    if X==0:
        print(count,0)
        break
    for j in array:
        if j^X in my_dict:
            curr = my_dict[j^X] + my_dict[j]
            if curr>=count:
                count = curr
                XOR_count = min(my_dict[j],XOR_count)
    if count ==temp:
        XOR_count = 0
    print(f"{count} {XOR_count}")

以下是一些示例输入和输出：

Sample Input  
3
3 2
1 2 3
5 100
1 2 3 4 5
4 1
2 2 6 6

Sample Output  
2 1
1 0
2 0

我正在解决的问题遇到了 time limit exceeded 错误。

我发现这个 link 在转换日志基础方面非常有用 (https://www.purplemath.com/modules/logrules5.htm)，我可以看到它是如何关联的，但我不能用它来获得我的上述问题的解决方案。

Answer 1

您可以通过编写一个函数 returns 给定基数中的数字总和和另一个函数 returns 以给定基数（基数 2）表示的数字来将问题分解为更小的问题在我下面的示例中为 36):

def digitSum(N,b=10):
    return N if N<b else N%b+digitSum(N//b,b)

digits = "0123456789abcdefghijklmnopqrstuvwxyz"
def asBase(N,b):
    return "" if N==0 else asBase(N//b,b)+digits[N%b]

def lowestBase(N,a,b):
    return asBase(N, min(range(a,b+1),key=lambda c:digitSum(N,c)) )

输出：

print(lowestBase(216,2,7))
1000     # base 6

print(lowestBase(216,2,5))
11011000 # base 2

请注意，如果您要处理大于 base^1000 的数字并且不希望处理递归深度限制

这是 digitSum 的过程版本（以避免递归限制）：

def digitSum(N,b=10):
    result = 0
    while N:
        result += N%b
        N //=b
    return result

并且只返回基数（不是编码后的数字）：

def lowestBase(N,a,b):
    return min(range(a,b+1),key=lambda c:digitSum(N,c))

# in which case you don't need the asBase() function at all.

进行这些更改后，在不到 60 毫秒的时间内返回 2 到 1000 碱基范围内的结果：

lowestBase(10**250+1,2,1000)  --> 10 in 57 ms

lowestBase(10**1000-1,2,1000) --> 3 in 47 ms

我不知道“非常大”有多大，但对于数百万个碱基来说它仍然是亚秒级的（但对于相对较小的数字）：

lowestBase(10**10-1,2,1000000) --> 99999 in 0.47 second

lowestBase(10**25-7,2,1000000) --> 2 in 0.85 second

[编辑]优化

通过为 digitSum() 函数提供最大总和，您可以使其在超过该最大值时立即停止计数。这将允许 lowestBase() 函数根据其当前最佳（迄今为止的最小总和）更有效地获得潜在的改进。向后遍历基数也有更好的机会更快地达到小数字和（因此利用 digitSum() 的 maxSum 参数）：

def digitSum(N,b=10,maxSum=None):
    result = 0
    while N:
        result += N%b
        if maxSum and result>=maxSum:break
        N //= b
    return result

def lowestBase(N,a,b):
    minBase = a
    minSum  = digitSum(N,a)
    for base in range(b,a,-1):
        if N%base >= minSum: continue # last digit already too large
        baseSum = digitSum(N,base,minSum)
        if baseSum < minSum:
            minBase,minSum = base,baseSum
            if minSum == 1: break
    return minBase

在大多数情况下，这应该会产生显着的性能改进。

是否存在一种算法可以在恒定时间内将一个（以 10 为底的）数字转换为另一个任意基数的数字？

Does an algorithm exist that converts a (base 10) number to into another number for any base in constant time?

python

time-limiting