algorithm - 计算具有数字 S 的大 A 和 B 之间的整数

Question

我正在尝试计算范围 A 到 B 之间具有数字总和 S(假设 S=60)的整数。

A 和 B 的范围从 1 到 10^18。

设 X 为数字，直到 Y 我们必须计算整数。

X = x1 x2 ... xn - 1 xn 和 Y = y1 y2 ... yn - 1 yn，其中 xi 和 yi 是 X 和 Y 的十进制数。

leftmost_lo 作为 xi < yi 的最小 i。如果没有这样的 i，我们将 leftmost_lo 定义为 n + 1。类似地，我们将 leftmost_hi 定义为 xi > yi 的最小 i，否则为 n + 1。

函数 count 返回具有属性 X ≤ Y 且 X 的数字和为 60 的整数 X 的数量 f(Y)。

根据上面的定义，令 n 为 Y 的位数，y[i] 为 Y 的第 i 个十进制数字。下面的递归算法解决了这个问题:

    count(i, sum_so_far, leftmost_lo, leftmost_hi):
       if i == n + 1:
       # base case of the recursion, we have recursed beyond the last digit
       # now we check whether the number X we built is a valid solution
        if sum_so_far == 60 and leftmost_lo <= leftmost_hi:
          return 1
        else: 
          return 0
     result = 0
     # we need to decide which digit to use for x[i]
     for d := 0 to 9
        leftmost_lo' = leftmost_lo
        leftmost_hi' = leftmost_hi
        if d < y[i] and i < leftmost_lo': leftmost_lo' = i
        if d > y[i] and i < leftmost_hi': leftmost_hi' = i
       result += count(i + 1, sum_so_far + d, leftmost_lo', leftmost_hi')
    return result






Compute the number f(Y) of integers X with the property X ≤ Y and X has the digit sum 60

现在我们有 f(Y) = count(1, 0, n + 1, n + 1) 并且我们已经解决了问题。运行时

对于这个特定的实现是 O(n^4)。

我从这个链接理解了这个概念。 How to count integers between large A and B with a certain property?

但无法理解如何优化它。

现在如何针对这个特定问题将其优化为 O(n) 解决方案。

谁能帮帮我。

Answer 1

首先，您可以注意到，如果您有一个函数 F，它返回整数 <= A 且数字总和为 S，则 A 和 B 之间具有数字总和 S 的整数个数为 F(B)-F( A-1).

然后定义一些符号:

• n(A) 表示由所有 9 组成的数字，其位数与 A) 相同。例如，n(123) = 999。
• A[0]表示A最左边的数字
• A[1:] 表示去掉最左边数字的 A。

然后你有这些关系，一次做一个数字，并注意到可能是你匹配 A 的第一个数字，或者你在那里放一个较低的数字(然后对于递归情况，你​​可以用 A 替换全9)。

F(S, A) = 1 if S = 0
F(S, A) = 0 if S < 0 or A = 0
otherwise F(S, A) =
    F(S-A[0], A[1:])
    + F(S-0, n(A[1:])) + F(S-1, n(A[1:])) + ... + F(S-A[0]-1, n(A[1:]))

这为您提供了这段代码(带有缓存以避免多次计算同一事物):

def count1(S, digits, nines, k, cache):
    if S <= 0 or k == len(digits): return S==0
    key = (S, nines, k)
    if key not in cache:
        dk = 9 if nines else digits[k]
        cache[key] = sum(count1(S-i, digits, nines or i<dk, k+1, cache)
                         for i in xrange(dk+1))
    return cache[key]

def count(S, A):
    return count1(S, map(int, str(A)), False, 0, {})

def count_between(S, A, B):
    return count(S, B) - count(S, A-1)

print count_between(88, 1, 10**10)

缓存最终的最大大小为 S * 2 * len(str(A))，每件事都计算一次，这给了你复杂性:O(S * log_10(A))。