PROBLEM LINK:
Author: Utkarsh
Tester:
Editorialist: Jingbo Shang, Anudeep
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given a string S which has ‘0’ - ‘9’. Find number of substrings, which when represented in base 10, whose remainder under mod M equals to L.
EXPLANATION:
Let F[i][j] denote the number of substrings ended at i-th character and the value mod M equals to j.
Therefore, we can try to extend F[i][j] to F[i + 1][(j * 10 + S[i + 1]] % 10] by simply add the next character. Or, one can also take the single character i+1-th into account.
So, we can formally have the algorithm as following:
- Initially, F[i][S[i] % M] is 1. Because we can only choose the single character.
- Then, F[i + 1][(j * 10 + S[i + 1]] % 10] += F[i][j], by extending substrings.
- The final answer should be the sum of F[1…|S|][L].
This algorithm’s time complexity is O(|S|L), which is efficient enough for this problem.
AUTHOR’S AND TESTER’S SOLUTIONS:
The links will be fixed soon.
Author’s solution can be found here.
Tester’s solution can be found here.