Unlucky number 13
<p>I came accorss this problem <a href="http://qa.geeksforgeeks.org/4344/the-unlucky-13" rel="nofollow">Unlucky number 13! </a> recently but could not think of efficient solution this.</p>

<h3>Problem statement :</h3>

<p>N is taken as input. </p>

<blockquote>
  <p>N can be very large 0&lt;= N &lt;= 1000000009</p>
</blockquote>

<p>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.</p>

<pre><code># Example:

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

# N =1 :
# output : 10 (0-9 without 13 number)
</code></pre>

<p>My solution:</p>

<pre><code>N = int(raw_input())

if N &lt; 2:
    print 10

else:
    without_13 = 10

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

<h2>Output</h2>

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

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

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

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

<p>Base cases:</p>

<pre><code>f(0) = 1
g(0) = 0
f(1) = 10
g(1) = 0
</code></pre>

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

<p>E.g. for g(5):</p>

<pre><code>g(5) = 10^(n-2) + 10^(n-2) + f(2)*10^(n-4) + f(3)*10^(n-5)
</code></pre>

<p>We can rewrite that to look the same everywhere:</p>

<pre><code>g(5) = f(0)*10^(n-2) + f(1)*10^(n-3) + f(2)*10^(n-4) + f(3)*10^(n-5)
</code></pre>

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

<p>In Python:</p>

<pre><code>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
</code></pre>

<p>The <code>lru_cache</code> is optional, but often a good idea when working with recursion.</p>

<hr>

<pre><code>&gt;&gt;&gt; [f(n) for n in range(10)]
[1, 10, 99, 980, 9701, 96030, 950599, 9409960, 93149001, 922080050]
</code></pre>

<p>The results are instant and <s>it works for very large numbers</s>.</p>

python