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>This a P&amp;C problem. I'm going to assume 0 is valid string and so is 00, 000 and so on, each being treated distinct from the other.</p>

<p>The total number of strings not containing 13, of length N, is unsurprisingly given by:</p>

<pre><code>(Total Number of strings of length N) - (Total number of strings of length N that have 13 in them)
</code></pre>

<p>Now, the Total number of strings of length N is easy, you have 10 digits and N slots to put them in: <code>10^N</code>.</p>

<p>The number of strings of length N with 13 in them is a little trickier.
You'd think you can do something like this:</p>

<pre><code>=&gt; (N-1)C1 * 10^(N-2)
=&gt; (N-1) * 10^(N-2)
</code></pre>

<p>But you'd be wrong, or more accurately, you'd be over counting certain strings. For example, you'd be over counting the set of string that have two or more 13s in them.</p>

<p>What you really need to do is apply the <a href="https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" rel="nofollow">inclusion-exclusion principle</a> to count the number of strings with 13 in them, so that they're all included once.</p>

<p>If you look at this problem as a set counting problem, you have quite a few sets:</p>

<pre><code>S(0,N): Set of all strings of Length N.
S(1,N): Set of all strings of Length N, with at least one '13' in it.
S(2,N): Set of all strings of Length N, with at least two '13's in it.
...
S(N/2,N): Set of all strings of Length N, with at least floor(N/2) '13's in it.
</code></pre>

<p>You want the set of all strings with 13 in them, but counted at most once. You can use the inclusion-exclusion principle for computing that set.</p>

python