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>In fact this question is more about math than about python.
For N figures there is 10^N possible unique strings. To get the answer to the problem we need to subtract the number of string containing "13". 
If string starts from "13" we have 10^(N-2) possible unique strings. If we have 13 at the second possition (e.i. a string like x13...), we again have 10^(N-2) possibilities. But we can't continue this logic further as this will lead us to double calculation of string which have 13 at different possitions. For example for N=4 there will be a string "1313" which we will calculate twice. To avoid this we should calculate only those strings which we haven't calculated before. So for "13" on possition <code>p</code> (counting from 0) we should find the number of unique string which don't have "13" on the left side from <code>p</code>, that is for each p 
number_of_strings_for_13_at_p = total_number_of_strings_without_13(N=p-1) * 10^(N-p-2)
So we recursevily define the total_number_of_strings_without_13 function.</p>

<p>Here is the idea in the code:</p>

<pre><code>def number_of_strings_without_13(N):
    sum_numbers_with_13 = 0
    for p in range(N-1):
        if p &lt; 2:
            sum_numbers_with_13 += 10**(N-2)
        else:
            sum_numbers_with_13 += number_of_strings_without_13(p) * 10**(N-p-2)

    return 10**N - sum_numbers_with_13
</code></pre>

<p>I should say that <code>10**N</code> means 10 in the power of N. All the other is described above. The functions also has a surprisingly pleasent ability to give correct answers for N=1 and N=2.</p>

<p>To test this works correct I've rewritten your code into function and refactored a little bit:</p>

<pre><code>def number_of_strings_without_13_bruteforce(N):
    without_13 = 0
    for i in range(10**N):
        if str(i).count("13"):
            continue
        without_13 += 1
    return without_13

for N in range(1, 7):
    print(number_of_strings_without_13(N),
          number_of_strings_without_13_bruteforce(N))
</code></pre>

<p>They gave the same answers. With bigger N bruteforce is very slow. But for very large N recursive function also gets mush slower. There is a well known solution for that: as we use the value of <code>number_of_strings_without_13</code> with parameters smaller than N multiple times, we should remember the answers and not recalculate them each time. It's quite simple to do like this:</p>

<pre><code>def number_of_strings_without_13(N, answers=dict()):
    if N in answers:
        return answers[N]

    sum_numbers_with_13 = 0
    for p in range(N-1):
        if p &lt; 2:
            sum_numbers_with_13 += 10**(N-2)
        else:
            sum_numbers_with_13 += number_of_strings_without_13(p) * 10**(N-p-2)

    result = 10**N - sum_numbers_with_13
    answers[N] = result
    return result
</code></pre>

python