Counting number contain 14 on n-digit number less than 1 second(yodi.polatic.me)

1 pointsby yodi11 ปีที่แล้ว2 comments

yodi.polatic.me

Counting number contain 14 on n-digit number less than 1 second

http://yodi.polatic.me/counting-number-contain-14-on-digit-number-in-less-than-1-second/

1 comments

dalke11 ปีที่แล้ว

I didn't understand the title. I thought it would be a math trick to determine if a number was divisible by 14, in your head. (Eg, check if the number is even, and use the technique for testing for divisibility by 7.)

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

yodi11 ปีที่แล้ว

@dalke that's neat linear rewrite!