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>I get the feeling that this question is designed with the expectation that you would initially instinctively do it the way you have. However, I believe there's a slightly different approach that would be faster.</p>

<p>You can produce all the numbers that contain the number 13 yourself, without having to loop through all the numbers in between. For example:</p>

<p>2 digits:
13</p>

<p>3 digits position 1:
113
213
313 etc.</p>

<p>3 digits position 2: 131
132
133 etc.</p>

<p>Therefore, you don't have to check all the number from 0 to n*9. You simply count all the numbers with 13 in them until the length is larger than N.</p>

<p>This may not be the fastest solution (in fact I'd be surprised if this couldn't be solved efficiently by using some mathematics trickery) but I believe it will be more efficient than the approach you have currently taken.</p>

python