如何在python中以更小的时间复杂度解决数字序列范围的总和？

Question

数字之间所有数字的总和

Kriti 有两个号码，她的补习老师给了她一个任务。任务是，她想找到出现在这两个数字之间的所有数字的总和。

For Ex:

Num1 = 8 and Num2 = 13

Output: 27

(8 + 9 + 1 + 0 + 1 + 1 + 1 + 2 + 1 +3)

输入格式

输入数字1 输入数字2

约束条件

0 <= 数字 1 <=1000000000

数字 1 <= 数字 2 <=1000000000

（不允许负数和小数）

输出格式

显示出现在 Number1 和 Number2 之间的所有数字的总和

Sample Input 0

8
13
Sample Output 0

27

我的代码

a=int(input())
b=int(input())
ls=0
lst=[]
s=0

for i in range(a,b+1):
    lst.append(i)
    
for i in lst:
    if i<10:
        s=s+i
    else:
        for j in str(i):
            s=s+int(j)
print(s)

这段代码几乎清除了5/7个测试用例，但剩下两个用例的问题是数字范围的值是1000000000，如果输入的数字最大会显示运行时错误如何解决这个问题的有效时间与给定的约束约束。我在这里提到的问题是一个hackerrank平台，比赛是由我的大学工作人员组织的，一个小时前就结束了

Answer 1

您的第一个 for 循环绝对没有用。你应该只是迭代 range(a, b + 1) 不要把它放在列表中 - 这使得解释器将所有值保存在内存中，而你在任何时间点只需要一个，这就是你必须使用范围的原因。这将节省大量时间和内存。

除此之外，计算可能只是略有改进。这是我想出的：

for i in range(a, b + 1):
    s += sum(map(int, str(i)))

Answer 2

所以我想我会这样做：

a = int(input()) 
b = int(input()) 

result = 0

for i in range(a, b+1): 
    # so here we want to get the digits of i and add them up
    current_length=len(str(i)) 
    if current_length == 1:
        result+=int(i) 
    else if current_length > 1:
        for k in str(i).split(""):
            result += int(k) 

print(result)

我认为这可能比你的方法更快，但我不确定，你可能还需要稍微调整一下这段代码，因为我在我的 phone 上做了它，但无法真正测试它。

Answer 3

您不需要列表来跟踪数字。您只需要运行的总和。您可以将每个数字转换为字符串。该字符串是可迭代的，可让您找到各个数字的总和。

sum = 0
for i in range(a, b + 1):
    digits = str(i)
    for d in digits:
        sum += int(d)

Answer 4

如果你从数字位置的角度来看，你可以达到 O(log10 N)。

def sumDigits(n1,n2):
    if n2==0 or n1>n2: return 0
    p1,d1 = divmod(n1,10)        # extract last digits
    p2,d2 = divmod(n2,10)        # and prefixes
    if p1==p2:
        # same prefix: sum of last digits, digit count * sum of prefix digits
        return sum(range(d1,d2+1)) + (d2-d1+1)*sumDigits(p1,p2)
    else:
        # different prefixes: recurse lower, upper, middle ranges
        return sumDigits(p1*10+d1,p1*10+9)  \
             + sumDigits(p2*10,   p2*10+d2) \
             + sumDigits(p1+1,p2-1)*10 + (p2-p1-1)*45 # full middle range

对于每个数字位置，您可以通过隔离较低、中间和较高部分范围并乘以中间前缀的数字总和来递归地执行计算。

例如：从 1234 到 4567

如果数字在最后一位数字之前有相同的前缀，那么我们只需要计算两个数字之间最后一位数字的总和并递归前缀中的数字总和（每个数字都会出现一次范围内的最后一位）
否则，将问题分解为下、中、上三个范围：
- 1234-1239 ... 124x-455x ... 4560-4567
中间部分将包含 124x 到 455x 范围内每个数字的所有结尾数字 (0...9)。
所以最后的数字部分将有45（∑0..9）332次（456-124）的总和。
中间范围内的每个前缀将出现 10 次（每个结尾数字一次）
因此我们可以使用 sumDigits(124,455) * 10 + (456-124) * 45
1234-1239 和 4560-4567 范围可以通过递归计算（根据定义它们有一个共同的前缀）

输出：

sumDigits(8,13)                # 27
sumDigits(1234,4567)           # 52723
sumDigits(123456789,987654321) # 35514403389

验证：

sum(sum(map(int,str(n))) for n in range(8,13+1))      # 27
sum(sum(map(int,str(n))) for n in range(1234,4567+1)) # 52723

sum(sum(map(int,str(n))) for n in range(123456789,987654321+1))# takes too long

如何在python中以更小的时间复杂度解决数字序列范围的总和？

How to solve sum of sequence range of digits with less time complexity in python?

python

loops

list

python-2.7

python-3.x