Unlucky number 13

Question

I came to this problem. Unlucky number 13! recently, but could not come up with an effective solution to this issue.

Description of the problem:

N is taken as input.

N can be very large 0 <= N <= 1000000009

Find the total number of lines that consist of exactly N characters that do not include "13". Strings can contain any integer from 0 to 9, repeated any number of times.

# Example: # N = 2 : # output : 99 (0-99 without 13 number) # N =1 : # output : 10 (0-9 without 13 number) 

My decision:

 N = int(raw_input()) if N < 2: print 10 else: without_13 = 10 for i in range(10, int('9' * N)+1): string = str(i) if string.count("13") >= 1: continue without_13 += 1 print without_13 

Output

The output file should contain the answer to each request in a new line modulo 1000000009.

Any other effective way to solve this problem? My solution gives a time limit on the coding site.

Answer 1

I think this can be solved by recursion:

 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 

Base cases:

• ans(0) = 1
• ans(1) = 10

The implementation is pretty fast even for large inputs like 10^9 (which is expected because its complexity is O(log[n]) instead of O(n) , like other answers):

 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 & 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) 

Online demo

Explanation:

Let string s have an even number of digits "n".
Let ans(n) be the answer for entering n , that is, the number of lines without substring 13 in them.
Therefore, the answer for string s with length n can be written as multiplying the answer for the first half of the string ( ans([n/2]) ) and the answer for the second half of the string ( ans([n/2]) ), minus the number of cases when line 13 appears in the middle of the number n , i.e. when the last digit of the first half is 1 and the first digit of the second half is 3 .

This can be expressed mathematically as:

 ans(n) = ans([n/2])^2 - ans([n/2]-1)*2 

Similarly, for cases when the input number n is odd, we can obtain the following equation:

 ans(n) = ans([n/2]+1)*ans([n/2]) - ans([n/2])*ans([n/2]-1) 

Answer 2

It seems to me that this question is designed with the expectation that you will initially instinctively do it the way you do. However, I believe that there is a slightly different approach that will be faster.

You can produce all numbers that contain number 13 yourself, without having to iterate over all the numbers between them. For instance:

2 digits: 13

3 digits of position 1: 113 213 313, etc.

3 digits of position 2: 131 132 133, etc.

Therefore, you do not need to check the whole number from 0 to n * 9. You just count all the numbers with 13 in them, as long as the length is greater than N.

This may not be the fastest solution (in fact, I would be surprised if this could not be solved efficiently using some mathematical tricks), but I believe that it will be more effective than the approach that you currently do.

Answer 3

This is a P&C problem. I am going to assume that 0 is a valid string, as well as 00,000, etc., each of which is processed separately from the other.

The total number of lines not containing 13, length N, is not surprisingly determined by the expression:

 (Total Number of strings of length N) - (Total number of strings of length N that have 13 in them) 

Now the total number of lines of length N is easy, you have 10 digits and N slots to put them in: 10^N

The number of lines N with 13 in them is a bit more complicated. You think you can do something like this:

 => (N-1)C1 * 10^(N-2) => (N-1) * 10^(N-2) 

But you are mistaken, or rather, you will count several lines. For example, you would have to count a set of rows in which there are two or more 13.

What you really need to do is apply the inclusion exclusion principle to count the number of rows with 13 in them, all included once.

If you consider this problem as a given counting task, you have quite a few sets:

 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 in it. ... S(N/2,N): Set of all strings of Length N, with at least floor(N/2) '13 in it. 

You need a set of all lines with 13 in them, but it counts no more than once. You can use the inclusion exclusion principle to compute this set.

Answer 4

Actually this question is more related to math than to python. For N numbers, there are 10 ^ N possible unique strings. To get the answer to the problem, we need to subtract the number of lines containing "13". If the line starts with "13", we have 10 ^ (N-2) possible unique lines. If in second place there are 13 (for example, a line like x13 ...), we again have 10 ^ (N-2) possibilities. But we cannot continue this logic further, as this will lead us to double-evaluate a string having 13 for different values. For example, for N = 4 there will be a line "1313", which we will calculate twice. To avoid this, we must calculate only those rows that we have not yet calculated. So, for "13" by the possibilities of p (counting from 0) we must find the number of a unique row that does not have "13" on the left side of p , that is, for each p number_of_strings_for_13_at_p = total_number_of_strings_without_13 (N = p-1) * 10 ^ (Np-2) Therefore, we recursively define the function total_number_of_strings_without_13.

Here is the idea in the code:

 def number_of_strings_without_13(N): sum_numbers_with_13 = 0 for p in range(N-1): if p < 2: sum_numbers_with_13 += 10**(N-2) else: sum_numbers_with_13 += number_of_strings_without_13(p) * 10**(Np-2) return 10**N - sum_numbers_with_13 

I must say that 10**N means 10 in capacity N. All the others are described above. Functions also have an amazingly nice ability to give correct answers for N = 1 and N = 2.

To test this, I fixed my code in a function and reworked a bit:

 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)) 

They gave the same answers. With a larger N, bruteforce happens very slowly. But for a very large N, the recursive function also becomes slower. There is a well-known solution for this: since we use the value number_of_strings_without_13 with parameters smaller than N several times, we must remember the answers and not recount them every time. This is pretty simple to do:

 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 < 2: sum_numbers_with_13 += 10**(N-2) else: sum_numbers_with_13 += number_of_strings_without_13(p) * 10**(Np-2) result = 10**N - sum_numbers_with_13 answers[N] = result return result 

Answer 5

Let f(n) be the number of sequences of length n that do not have “13” in them, and g(n) be the number of sequences of length n that have “13” in them.

Then f(n) = 10^n - g(n) (in mathematical notation), since the number of possible sequences ( 10^n ) minus those that contain "13".

Base cases:

 f(0) = 1 g(0) = 0 f(1) = 10 g(1) = 0 

When searching for sequences with “13,” the sequence may have “13” at the beginning. This will take into account the 10^(n-2) possible sequences with "13" in them. He may also have “13” in second position, again considering the 10^(n-2) possible sequences. But if there is a “13” in the third position, and we assumed that there would also be 10^(n-2) possible sequences, we could have those that already had a “13” in the first position twice. Therefore, we must subtract them. Instead, we count 10^(n-4) times f(2) (because these are exactly combinations in the first two positions in which there is no “13”).

eg. for g (5):

 g(5) = 10^(n-2) + 10^(n-2) + f(2)*10^(n-4) + f(3)*10^(n-5) 

We can rewrite this to look the same everywhere:

 g(5) = f(0)*10^(n-2) + f(1)*10^(n-3) + f(2)*10^(n-4) + f(3)*10^(n-5) 

Or just the sum f(i)*10^(n-(i+2)) with i from 0 to n-2 .

In Python:

 from functools import lru_cache @lru_cache(maxsize=1024) def f(n): return 10**n - g(n) @lru_cache(maxsize=1024) def g(n): return sum(f(i)*10**(n-(i+2)) for i in range(n-1)) # range is exclusive 

lru_cache is optional, but is often a good idea when working with recursion.

---

 >>> [f(n) for n in range(10)] [1, 10, 99, 980, 9701, 96030, 950599, 9409960, 93149001, 922080050] 

The results are instant and work for very large numbers .

Answer 6

Thanks to the comment L3viathan is now clear. The logic is beautiful.

Suppose that a(n) is the number of lines of n digits without "13" in it. If we know all the good lines for n-1 , we can add another digit to the left of each line and calculate a(n) . Since we can combine the previous digits with any of the 10 new ones, we get 10*a(n-1) different lines. But we have to subtract the number of lines that now begin with "13", which we mistakenly summed as OK in the previous step. There are a(n-2) such incorrectly added rows. So, a(n+1) = 10*a(n-1) - a(n-2) . That's all. So simple.

Interestingly, this sequence can be calculated without iterations using the formula https://oeis.org/A004189 But this practically does not help, since the formula requires floating point calculations, which will lead to rounding and will not work for large n (will give answer with some error).

However, the original sequence is fairly easy to compute, and it does not need to save all previous values, only the last two. So here is the code

 def number_of_strings(n): result = 0 result1 = 99 result2 = 10 if n == 1: return result2 if n == 2: return result1 for i in range(3, n+1): result = 10*result1 - result2 result2 = result1 result1 = result return result 

This is several orders of magnitude faster than my previous sentence. And the memory consumption is now just O (n)

PS If you run this using Python2, it is better to change range to xrange