Subarray Sums Divisible by K

Problem

Count the subarrays whose sum is divisible by k, where values may be negative.

Maintain counts of prefix sums modulo k and, for each new prefix, add the number of earlier prefixes with the same residue. Python's modulo keeps every residue non-negative.

Hint

A subarray between two equal prefix residues has a sum divisible by k.

Test cases

case 1

in: [[4,5,0,-2,-3,1],5]

expected: 7

case 2

in: [[5],5]

expected: 1

case 3

in: [[0,0,0],3]

expected: 6

case 4

in: [[-1,2,9],2]

expected: 2

case 5

in: [[],5]

expected: 0

Starter codePython

def subarrays_divisible_by_k(nums, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor