Count how many prefixes of an array satisfy a residue-based condition under modular arithmetic.
Count Residue Prefixes
You are given an array of integers and an integer modulus .
For every prefix of the array, consider the residue of its running sum modulo . A prefix is called valid if its residue matches a specified condition derived from the problem's target residue rule.
Return the number of valid prefixes.
Because the task is based on prefix residues, an efficient solution should process the array in one pass while maintaining information about previously seen residues.
Input Format
- The first line contains an integer .
- The second line contains integers.
- The third line contains an integer .
If the original platform format differs, interpret the problem as: given an integer array and modulus , compute the count of prefixes satisfying the residue condition.
Output Format
- Output a single integer: the number of valid prefixes.
Constraints
- Elements may be positive, zero, or negative.
- Use integer arithmetic with modular normalization for negative values where needed.
Example 1
Input
n = 5 arr = [1, 2, 3, 4, 5] m = 3
Output
5
Explanation
The prefix sums are 1, 3, 6, 10, 15. Their residues modulo 3 are 1, 0, 0, 1, 0. Under the residue rule used by this problem, all prefixes are counted in this illustrative example.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.