CODEWITHSUNDEEP
python
Lancer
Lancer

Reputation: 19

Time limit,how to reduce the code execution time for large numbers to a billion?

a, b = map(int, input().split())
s = 0
for i in range(a, b + 1):
    g = 0
    while i != 0:
        k = i % 10
        g = g + k
        i = i // 10
    if g % 2 == 0:
        s = s + 1      
print(s)

The task itself:Count the number of natural numbers on the segment from a to b, the sum of the digits of which is even.

Upvotes: 2

Views: 133

Answers (2)

Michael Szczesny
Michael Szczesny

Reputation: 5036

You can use (end-start)//2 for full blocks of n*10+[0...9] inside the range and compute the small rests with your algorithm.

def q1(a,b):
    s = 0
    for i in range(a, b + 1):
        g = 0
        c = i
        while i != 0:
            k = i % 10
            g = g + k
            i = i // 10
        if g % 2 == 0:
            s = s + 1      
    return s

def q2(a,b):
    br = b%10
    ar = 10 - a%10
    return q1(a, a+ar-1) + ((b - br) - (a + ar)) // 2 + q1(b-br,b)

I tested the implementation with

import random
for _ in range(1000):
    a = random.randint(1,1000)
    b = random.randint(100,100000)
    assert q1(a,a+b) == q2(a,a+b), 'not the same result'

Benchmark

%timeit q1(10,10000)         #=4995 in ~O(n^2)
# 100 loops, best of 5: 7.58 ms per loop
%timeit q2(10,1_000_000_000) #499999995 in ~O(1)
# 100000 loops, best of 5: 7.17 µs per loop

Upvotes: 1

Eumel
Eumel

Reputation: 1433

The idea here is not to loop through everything.

The sum of digits of every second number is even:

101 -> even
102 -> odd
103 -> even

So to find the amount of numbers that have an even sum of digits all you have to do is (start-end)/2and then account for the edge cases, basically if the number you start and end on have even or odd sums.

Edit: I missed one of the weirdnesses at the 10s. The example beeing 29 and 30 which are both odd. So to amend that, every block of 10 numbers like 30-39 has 5 even and 5 odds. That increases the edge case you need to consider to a couple numbers befor you hit the first multiple of 10 and after you hit your last multiple of 10 - 1.

Upvotes: 4

Related Questions