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 think this can be solved via recursion:</p>

<pre><code>ans(n) = { ans([n/2])^2 - ans([n/2]-1)^2 }, if n is even
ans(n) = { ans([n/2]+1)*ans([n/2]) - ans([n/2])*ans([n/2]-1) }, if n is odd
</code></pre>

<p>Base Cases:</p>

<ul>
<li><code>ans(0)</code> = 1</li>
<li><code>ans(1)</code> = 10</li>
</ul>

<p>It's implementation is running quite fast even for larger inputs like <code>10^9</code> ( which is expected as its complexity is <code>O(log[n])</code> instead of <code>O(n)</code> like the other answers ):  </p>

<pre><code>cache = {}

mod = 1000000009

def ans(n):
    if cache.has_key(n):
        return cache[n]

    if n == 0:
        cache[n] = 1
        return cache[n]
    if n == 1:
        cache[n] = 10
        return cache[n]

    temp1 = ans(n/2)
    temp2 = ans(n/2-1)

    if (n &amp; 1) == 0:
        cache[n] = (temp1*temp1 - temp2*temp2) % mod
    else:
        temp3 = ans(n/2 + 1)
        cache[n] = (temp1 * (temp3 - temp2)) % mod

    return cache[n]

print ans(1000000000)
</code></pre>

<p><a href="http://ideone.com/TNqxJw" rel="nofollow">Online Demo</a></p>

<p><strong>Explanation:</strong></p>

<p>Let a string <code>s</code> have even number of digits 'n'.<br>
Let <code>ans(n)</code> be the answer for the input <code>n</code>, i.e. the number of strings without the substring <code>13</code> in them.<br>
Therefore, the answer for string <code>s</code> having length <code>n</code> can be written as the multiplication of the answer for the first half of the string (<code>ans([n/2])</code>) and the answer for the second half of the string (<code>ans([n/2])</code>), minus the number of cases where the string <code>13</code> appears in the middle of the number <code>n</code>, i.e. when the last digit of the first half is <code>1</code> and the first digit of the second half is <code>3</code>.</p>

<p>This can expressed mathematically as:  </p>

<pre><code>ans(n) = ans([n/2])^2 - ans([n/2]-1)*2
</code></pre>

<p>Similarly for the cases where the input number <code>n</code> is odd, we can derive the following equation:  </p>

<pre><code>ans(n) = ans([n/2]+1)*ans([n/2]) - ans([n/2])*ans([n/2]-1)
</code></pre>

python