count '9's from 1 to n python optimization-CodePudding

def count_nines(n):
    x = list(map(str,range(n   1)))
    count = 0
    for i in x:
        c = i.count('9')
        count  = c 
    return count

Execution Timed Out (12000 ms)

How can i optimize this code ?

CodePudding user response：

Here's some working code (I tested it on some not too big numbers, and it returns the same results as yours) based on my comment:

def count_nines(n):
    if n==0:
        return 0
    k = len(str(n))-1
    leading_digit, remainder = divmod(n, 10**k)  # Thanks @Stef for this optimization
    return int(leading_digit*k*10**(k-1)   (remainder 1 if leading_digit==9 else 0)   count_nines(remainder))

Explanations

For starters, the numbers of nines (shortened as c9() hereafter) in 1-10^k is k * 10^(k-1); this is easy to prove by recurrence, but I'll just explain on an example: assuming c9(1000) = 300, the number of nines in the xxx part of numbers 0xxx, 1xxx ... 9xxx is equal to 10 * 300; add to that the number of 9 in 9xxx is 1000 (from 9000 to 9999), which yields c9(10000) = 10*300 1000 = 4000 .
Now imagine you want c9(7935) : you have 7 * 300 nines in numbers 1-7000, then 9*20 nines in numbers 7 000 to 7 900, then 36 leading nines in number 900 to 935, then ...

Example

cnt_nines(9254287593789050756)
Out[12]: 16880680640899572416

CodePudding user response：

What about use re.compile() and findall() could be an alternative:

def count_nines(n):
    p = re.compile('9')
    return len(p.findall(str(n)))