Difficulty: Easy | Acceptance: 65.60% | Paid: No Topics: Hash Table, String
You are given a string s consisting of digits and an integer m. Consider all prefixes of s. For each prefix, convert it to a number and compute its remainder when divided by m. Return the number of prefixes whose remainder is 0 (i.e., prefixes divisible by m).
- Examples
- Constraints
- Brute Force
- Iterative Modulo
Examples
Example 1
Input: s = "123", m = 5
Output: 0
Explanation:
- Prefix "1": 1 % 5 = 1
- Prefix "12": 12 % 5 = 2
- Prefix "123": 123 % 5 = 3
No prefix is divisible by 5.
Example 2
Input: s = "50", m = 5
Output: 2
Explanation:
- Prefix "5": 5 % 5 = 0
- Prefix "50": 50 % 5 = 0
Both prefixes are divisible by 5.
Example 3
Input: s = "0123", m = 5
Output: 1
Explanation:
- Prefix "0": 0 % 5 = 0
- Prefix "01": 1 % 5 = 1
- Prefix "012": 12 % 5 = 2
- Prefix "0123": 123 % 5 = 3
Only the first prefix is divisible by 5.
Constraints
1 <= s.length <= 10⁵
1 <= m <= 10⁹
s consists only of digits
Brute Force
Intuition For each prefix of the string, convert it to a number and check if it’s divisible by m.
Steps
- Iterate through each position in the string
- For each position, extract the prefix substring
- Convert the prefix to a number
- Check if the number is divisible by m
- Count the number of divisible prefixes
python
class Solution:
def countResiduePrefixes(self, s: str, m: int) -> int:
count = 0
for i in range(1, len(s) + 1):
prefix = int(s[:i])
if prefix % m == 0:
count += 1
return count
Complexity
- Time: O(n²) - converting each prefix to a number takes O(n) time, and we do this for n prefixes
- Space: O(n) - for storing the prefix substring
- Notes: This approach is inefficient for large strings and may overflow for very long prefixes
Iterative Modulo
Intuition Instead of converting each prefix to a number, we can compute the residue iteratively. For each new digit, the new residue is (old_residue * 10 + digit) % m. This avoids overflow and is much more efficient.
Steps
- Initialize residue to 0 and count to 0
- Iterate through each character in the string
- For each digit, update the residue: residue = (residue * 10 + digit) % m
- If the residue is 0, increment the count
- Return the count
python
class Solution:
def countResiduePrefixes(self, s: str, m: int) -> int:
count = 0
residue = 0
for ch in s:
residue = (residue * 10 + int(ch)) % m
if residue == 0:
count += 1
return count
Complexity
- Time: O(n) - single pass through the string
- Space: O(1) - only using a few variables
- Notes: This is the optimal solution, avoiding overflow and being very efficient