Unlucky number 13
<p>I came across this problem <a href="http://qa.geeksforgeeks.org/4344/the-unlucky-13" rel="nofollow noreferrer">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 &quot;13&quot;. 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(&quot;13&quot;) &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>