Unlucky number 13

Question

I came across this problem Unlucky number 13! recently but could not think of efficient solution this.

Problem statement :

N is taken as input.

N can be very large 0<= N <= 1000000009

Find total number of such strings that are made of exactly N characters which don't include "13". The strings may contain any integer from 0-9, repeated any number of times.

# Example:

# N = 2 :
# output : 99 (0-99 without 13 number)

# N =1 :
# output : 10 (0-9 without 13 number)

My solution:

N = int(raw_input())

if N < 2:
    print 10

else:
    without_13 = 10

    for i in range(10, int('9' * N)+1):
        string = str(i)
        if string.count("13") >= 1:
            continue
        without_13 += 1
    print without_13

Output

The output file should contain answer to each query in a new line modulo 1000000009.

Any other efficient way to solve this ? My solution gives time limit exceeded on coding site.

Answer 1

I think this can be solved via recursion:

ans(n) = { ans([n/2])^2 - ans([n/2]-1)^2 }, if n is even
ans(n) = { ans([n/2]+1)*ans([n/2]) - ans([n/2])*ans([n/2]-1) }, if n is odd

Base Cases:

• ans(0) = 1
• ans(1) = 10

It's implementation is running quite fast even for larger inputs like 10^9 ( which is expected as its complexity is O(log[n]) instead of O(n) like the other answers ):

cache = {}

mod = 1000000009

def ans(n):
    if cache.has_key(n):
        return cache[n]

    if n == 0:
        cache[n] = 1
        return cache[n]
    if n == 1:
        cache[n] = 10
        return cache[n]

    temp1 = ans(n/2)
    temp2 = ans(n/2-1)

    if (n & 1) == 0:
        cache[n] = (temp1*temp1 - temp2*temp2) % mod
    else:
        temp3 = ans(n/2 + 1)
        cache[n] = (temp1 * (temp3 - temp2)) % mod

    return cache[n]

print ans(1000000000)

Online Demo

Explanation:

Let a string s have even number of digits 'n'.
Let ans(n) be the answer for the input n, i.e. the number of strings without the substring 13 in them.
Therefore, the answer for string s having length n can be written as the multiplication of the answer for the first half of the string (ans([n/2])) and the answer for the second half of the string (ans([n/2])), minus the number of cases where the string 13 appears in the middle of the number n, i.e. when the last digit of the first half is 1 and the first digit of the second half is 3.

This can expressed mathematically as:

ans(n) = ans([n/2])^2 - ans([n/2]-1)*2

Similarly for the cases where the input number n is odd, we can derive the following equation:

ans(n) = ans([n/2]+1)*ans([n/2]) - ans([n/2])*ans([n/2]-1)

Answer 2

Let f(n) be the number of sequences of length n that have no "13" in them, and g(n) be the number of sequences of length n that have "13" in them.

Then f(n) = 10^n - g(n) (in mathematical notation), because it's the number of possible sequences (10^n) minus the ones that contain "13".

Base cases:

f(0) = 1
g(0) = 0
f(1) = 10
g(1) = 0

When looking for the sequences with "13", a sequence can have a "13" at the beginning. That will account for 10^(n-2) possible sequences with "13" in them. It could also have a "13" in the second position, again accounting for 10^(n-2) possible sequences. But if it has a "13" in the third position, and we'd assume there would also be 10^(n-2) possible sequences, we could those twice that already had a "13" in the first position. So we have to substract them. Instead, we count 10^(n-4) times f(2) (because those are exactly the combinations in the first two positions that don't have "13" in them).

E.g. for g(5):

g(5) = 10^(n-2) + 10^(n-2) + f(2)*10^(n-4) + f(3)*10^(n-5)

We can rewrite that to look the same everywhere:

g(5) = f(0)*10^(n-2) + f(1)*10^(n-3) + f(2)*10^(n-4) + f(3)*10^(n-5)

Or simply the sum of f(i)*10^(n-(i+2)) with i ranging from 0 to n-2.

In Python:

from functools import lru_cache

@lru_cache(maxsize=1024)
def f(n):
    return 10**n - g(n)

@lru_cache(maxsize=1024)
def g(n):
    return sum(f(i)*10**(n-(i+2)) for i in range(n-1))  # range is exclusive

The lru_cache is optional, but often a good idea when working with recursion.

---

>>> [f(n) for n in range(10)]
[1, 10, 99, 980, 9701, 96030, 950599, 9409960, 93149001, 922080050]

The results are instant and it works for very large numbers.