Problem 333318 · medium · Phase 03 Linear Management & Searching

Stretches Divisible by k

prefix sums · modular arithmetic · hash map

Count the non-empty contiguous stretches of nums whose sum is divisible by k.

Examples

Input:  nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7
Explanation: [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3].

Input:  nums = [5], k = 5
Output: 1

Constraints

  • 1 <= len(nums) <= 10**5
  • -10**4 <= nums[i] <= 10**4, 2 <= k <= 10**4
  • Target complexity: O(n) time. Enumerating all stretches is too slow.

Goals

  • Reduce prefix totals modulo k
  • Count pairs of equal remainders with a frequency map
  • Handle negative remainders correctly
Starting Python…