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>Thanks to L3viathan's comment now it is clear. The logic is beautiful.</p>

<p>Let's assume <code>a(n)</code> is a number of strings of <code>n</code> digits without "13" in it. If we know all the good strings for <code>n-1</code>, we can add one more digit to the left of each string and calculate <code>a(n)</code>. As we can combine previous digits with any of 10 new, we will get <code>10*a(n-1)</code> different strings. But we must subtract the number of strings, which now starts with "13" which we wrongly summed like OK at previous step. There is <code>a(n-2)</code> of such wrongly adde strings. So <code>a(n+1) = 10*a(n-1) - a(n-2)</code>. That is it. Such simple.</p>

<p>What is even more interesting is that this sequence can be calculated without iterations with a formula <a href="https://oeis.org/A004189" rel="nofollow">https://oeis.org/A004189</a> But practically that doesn't helps much, as the formula requires floating point calculations which will lead to rounding and would not work for big n (will give answer with some mistake).</p>

<p>Nevertheless the original sequence is quite easy to calculate and it doesn't need to store all the previous values, just the last two. So here is the code</p>

<pre><code>def number_of_strings(n):
    result = 0
    result1 = 99
    result2 = 10
    if n == 1:
        return result2
    if n == 2:
        return result1
    for i in range(3, n+1):
        result = 10*result1 - result2
        result2 = result1
        result1 = result
    return result 
</code></pre>

<p>This one is several orders faster than my previous suggestion. And memory consumption is now just O(n)</p>

<p>P.S. If you run this with Python2, you'd better change <code>range</code> to <code>xrange</code></p>

python