2019 was an amazing year. I loved 2019 so much that I want to find 2019 everywhere. So, I found a random string S that contains digits 1-9. I want to find number of pairs of integers {i,j ∣ 1≤i≤j≤∣S∣} where characters between ith and jth positions form an integer which is a multiple of 2019.
Input Format
S
Constraints
1≤∣S∣≤2∗105
Output Format
Print the answer.
Sample Inputs:
Input
1817181712114
Output
3
Explanation
Three pairs - (1,5), (5,9), and (9,13) - form such integers:
18171 = 2019 * 9
12114 = 2019 * 6
Solution - Modular
A modular solution traversing reversed string is able to solve the problem. We first stores the frequency of prefix mod values (3 * 673), then we try to loop through the length of the string, getting their modular values.
If we got same mod value, then we prove that there's a substring which is the multiple of 2019.
After traversed all strings, output the counter.
from collections import defaultdict
def count_divisible_by_2019(s):
mod = 2019
count = 0
mod_count = defaultdict(int) # Stores frequency of prefix mod values
mod_count[0] = 1 # To handle cases where prefix itself is divisible
prefix = 0
power = 1 # To handle positional values correctly (like 10^0, 10^1, ...)
# Traverse the string from right to left (ensuring digit order remains)
for digit in reversed(s):
prefix = (prefix + int(digit) * power) % mod
count += mod_count[prefix] # If the same mod value was seen before, we found substrings
mod_count[prefix] += 1
power = (power * 10) % mod # Maintain correct positional contribution
return count
print(count_divisible_by_2019(input()))