time limit exceed in the code that sums the numbers

Question

in the question there will be a number taken from user. Up to that number, I want to find the sum of all numbers if the sum of that number's digits is odd. For example if the input is 13 then ; 1+3+5+7+9+10+12 = 47 should be the result. In order to prevent time limit exceed, question says "Since the answer might be too big, please print the answer in modulo 10^9+7"

Constraints 1 ≤ n < 10^17 (n is input)

Here is my code:

MOD = 1000000007
def getSum(number):
    total = 0
    while number > 0:
        total += number % 10
        number //= 10
    return (total % MOD) % 2

def sticker(number):
    stickerNeed = 0
    for oneDigit in range(1, number):
        if (getSum(oneDigit % MOD) == 1):
            stickerNeed += oneDigit
    return stickerNeed % MOD


number = int(input())
result = sticker(number)
print(result % MOD)

But it still cannot handle the really big numbers and gives time limit exceed. Can you help me out? What wrong with my code?

Answer 1

Surely, brute force is not right way for given range.

Instead think about the next:

1 3 5 7 9 10 12...18 21...29 30...98 100 102..108 111...199 201...999 1000 1002...

We can see that ever decade *0..*9 contains exactly 5 numbers with odd digit sum, but these numbers can start from *0 or from *1.

Aslo note that every hundred *0..*99 contains five decades starting from 0, and five decades starting from 1

Let's separate the end of series after last *00 value for simplicity and calculate their sum using function like your sticker but with corrected mistakes (your function gives wrong results).

Right function (not the fastest, but suitable for our purposes):

def sumofOdds(a, b):
    result = 0
    for i in range(a, b+1):
        t = i
        s = 0
        while t:
            s += t%10
            t //= 10
        if s%2:
            result += i
    return result

For example, for input 231, calculate sum for range 200..231 as described above, and for 1..199 as described below

But what about swarm of numbers before last *00?

Sum of these numbers is sum of arithmetic progression of the sequence 0,2,4,...*98 plus addition of 25 * number of hundreds (because every hundred contains 5 decades starting from 1 and they give 25 additional units). Note - this is one-liner formula.

Where to use MOD? In formula for arithmetic progression sum, after summation with 25 * number of hundreds, and after summation with "end of series" sum. But not in getSum and sticker

I hope these ideas will be useful for your solution

Test result:

46781934    #input
321669645   #by formula, calculated in microseconds
321669645   #by brute force, calculated in one minute

P.S. For range 10^17 we have to use modular aritmetics inside sumofOdds in languages without in-built support of big integers (Python works with such numbers well)

  if s%2:
     result = (result + i) % MOD