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.

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.