# TÓPICO

Tempo de execução. #### Wellerson Salvatore perguntou 10 months ago

Alguém sabe como diminuir o tempo de execução para esse problema? a unica forma que eu pensei vai levar muito tempo, nem testei enviar porquê sei que vai dar TLE pra casos como 10^12... segue o codigo:

``````n = int(input())
cont = 0
for i in range(1, n + 1):
a = str(i)
cont += a.count("1")
cont += a.count("7")
print(cont)``````

foi a unica forma que consegui pensar, se alguém tiver uma dica fico grato.

Lembre de não publicar soluções. Sua publicação pode ser revisada por nossos moderadores.

• #### feodorv respondido 10 months ago

Hm. That was a hint, that was not a solution. Let's consider the input number 15725. We can count offhand the answer for the interval [1...9999]: x is 4 (x is the number of digits of 9999) and the answer for the interval [1...9999] is 8000. Now we should consider the interval [10000...15725]. We can see that it consists of numbers 1#[0...5725] and contains 5726 times the number '1' and the interval [0...5725] (the answers for intervals [0...5725] and [1...5725] are the same ones). So you can reduce the task to smaller interval. Now you can consider the intervals [0...999], [1000...1999], [2000...2999], [3000...3999], [4000...4999], [5000...5725]. The answer for first five intervals are calculated by means of the given formula (here x = 3): 600 + (1000+600) + 600 + 600 + 600. Now you have 17726 in total and the interval [0...725] for further counting . You can continue this algorithm till zero interval.

This algorithm is not the only approach to the problem. Please, see the following sites:

``````https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property
https://codeforces.com/blog/entry/53960
https://www.geeksforgeeks.org/digit-dp-introduction/
``````
• #### feodorv respondido 10 months ago

It's a Digit DP problem. Hint: you can offhand count the number of 1 and 7 for N = (10^x)-1. It's

``2 * x * 10^(x-1) ``

For example:

``````40 for N = 99 (x=2)
14000000 for N = 9999999 (x=7)
2400000000000 for N = 999999999999 (x=12)``````
• #### Wellerson Salvatore respondido 10 months ago

I didn't understand it. How did you get the value of ' x '?

``#``

Eu não entendi... Como você obteve o valor de ' x '?