Skills101
← All coding problems

Subarrays With Sum Divisible by K

mediumArrays & Prefix Sums+20 XPTime limit 2s

Count the non-empty contiguous subarrays whose sum is divisible by k. (A sum of 0 counts — it is divisible by every k.)

Input:

  • line 1: n k
  • line 2: n integers (may be negative)

Output: the number of such subarrays (it can exceed 2³¹ — use 64-bit integers).

Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁴, −10⁴ ≤ a[i] ≤ 10⁴.

Think about it: a[l..r] is divisible by k exactly when the prefix sums at l − 1 and r leave the same remainder mod k. Count remainders in a map as you go. Careful: in C++/Java/JS, % of a negative number is negative — use ((x % k) + k) % k.

Sample input 1

6 5
4 5 0 -2 -3 1

Sample output 1

7

Sample input 2

1 9
5

Sample output 2

0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.