Counting subnumbers divisible by a given prime

Question

Assume we are given a number and a prime p. The goal is to count all subnumbers of number that are divisible by p. A subnumber of number is formed of any number of consecutive digits in the decimal representation of number. Here is my solution:

number = input()
p = int(input())
print([int(number[i : j]) % p for i in range(len(number)) for j in range(i + 1, len(number) + 1)].count(0))

Can this solution be made faster?

Here is the original source of the problem.

• superb rain: Thanks. Should be in the question, I did that already. Please also add the problem limits there. I'd have to rely on Google's translation to get it right.
• miracle173: I think you should mention that the length of the string is about 10^6 and the size of p is about 10^9

Answer 1

Let \$N_{i,j}\$ be the subnumber of \$N\$ from the \$i\$th digit (excluded) to the \$j\$th digit (included). Here, the first digit is the least significant one.

Let \$R_i = N \bmod 10^i \$. We have \$R_j-R_i=N_{i,j} * 10^i, 0\leq i < j \leq D(N)\$, where \$D(N)\$ is the number of digits in \$N\$. There are two cases.

• If \$p \nmid 10\$, then $$p \mid N_{i,j} \Leftrightarrow p\mid N_{i,j} * 10^i \Leftrightarrow p\mid R_j-R_i \Leftrightarrow R_j \equiv R_i \pmod{p}$$

In this case, we can compute \$R_i\bmod p\$ for all \$i=0,\ldots,D(N)\$, group them by values, count the number of pairs in each group and then take the sum. (Note: the implementation can simply count the size of each group \$|G|\$ using itertools.Counter and compute the number of pairs \$C_{|G|}^2\$)

• If \$p\mid 10\$, we have either \$p = 2\$ or \$p = 5\$. In this case, $$p \mid N_{i,j} \Leftrightarrow p \mid N_{i+1} $$ Here, \$N_{i+1}\$ is the \$(i+1)\$th digit of \$N\$. In other words, if \$p \mid N_{i+1} \$ holds, \$p \mid N_{i,j}\$ holds for all \$j\$ s.t. \$i<j\leq D(N)\$. It is easy to show that the final result is $$\sum_{0\leq i < D(N),,円p,円\mid,円 N_{i+1}}(D(N)-i)$$

The time complexity of this algorithm is \$\Theta(D(N))=\Theta(\log N)\$, which is better than the \$\Theta(D(N)^4)\$ solution in OP (see comments for explanation). Note that the runtime of the actual program depends on your implementation.

You may try to implement this approach yourself.

• Mohammad Ali Nematollahi: @GZ0 Although I know what you mean, completely, but my goal is to correct everything here. Consider \$ N = 123456 \$. Now what are \$ R_{3} \,ドル \$ R_{6} \$ and \$ N_{36}\$? I think we should assume another identity when both \$ i \$ and \$ j \$ are greater than or equal to \$ D(N) \$. Thanks
• GZ0: @MohammadAliNematollahi I slightly updated the notations and text to avoid potential confusions. As defined in my post, \$R_3 = N \bmod 10^3 = 456, R_6 = N \bmod 10^6 = 123456, N_{3,6}=123\$. \$R_i\$ is the last \$i\$ digits. \$N_{3,6}\$ is the 3rd (excluded) to 6th digit (included), starting from the right side of \$N\$ (note that the indexing starts with 1). So \$j\$ can be equal to \$D(N)\$. For this problem, we only need to consider \$i, j\$ such that \0ドル\leq i < j \leq D(N)\$ in the notation \$N_{i,j}\$. The other cases are not of our interest here.
• Mohammad Ali Nematollahi: GZ0 I changed my code due to your instructions. Now, it passes more tests but yet there are several tests with "time limit exceeded" error. Where can I put my code in order to be checked by you... Thanks in advance...
• GZ0: You can create a follow-up post and refer to this one. Meanwhile, @superbrain had implemented this (not sure why our previous exchanges in the comments were gone) so he should be able to help you as well. I think the most important aspect is the computation of \$R_i \bmod p\$. You need to do it incrementally rather than computing from scratch (so that the time complexity of each computation is \$\Theta(1)\,ドル not \$\Theta(D(n))\$).
• Mohammad Ali Nematollahi: I posted my new code here. Can you take a look?