Counting number contain 14 on n-digit number less than 1 second(yodi.polatic.me) |
Counting number contain 14 on n-digit number less than 1 second(yodi.polatic.me) |
Instead, it counts the number of numbers in a range which have a "14" in the base-10 expression, using Python code like:
len(["14" in str(i) for i in range(10**n)])
Followed by a more clever recursive solution: def counting(n):
if n == 2:
return 1
elif n < 2:
return 0
return 10 * counting(n-1) - counting(n-2) + 10**(n-2)
It ended there, but I'll continue a bit further. As with the recursive Fibonacci implementation, this takes exponential time in n - try counting(100). A linear rewrite gives: def counting2(n):
if n < 2:
return 0
prev = 0
curr = 1
for i in range(3, n+1):
prev, curr = curr, 10*curr - prev + 10**(i-2)
return curr
where counting2(100) = 6339...7499