All problems

Subarray Sums Divisible by K

Medium · prefix sum

You are given a list nums of integers, which may be negative, and a positive integer k.

A run is a block of one or more neighbouring numbers in the list, and its total is the sum of the numbers in the block. A total of 0 counts as divisible by k.

Return how many runs have a total divisible by k. Runs are told apart by where they sit in the list, so two runs with the same values in different places each count. If there are none, return 0.

Examples

Example 1

Input: nums = [3, 3, 3], k = 3

Output: 6

Every run has a total that is a multiple of 3, and there are 6 runs: three single numbers, two of length two and the whole list.

Example 2

Input: nums = [1, 2, 3], k = 3

Output: 3

The runs [1, 2], [3] and [1, 2, 3] have totals 3, 3 and 6.

Example 3

Input: nums = [-1, 2, 9], k = 5

Output: 1

Only the whole list qualifies, with total 10. The other totals are -1, 2, 9, 1 and 11.

Constraints