Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Hashing & Two Pointers

Subarray Sums Divisible by K

Medium · Hashing & Two Pointers · Asked at Amazon, Microsoft, Twilio, Goldman Sachs

Count the non-empty subarrays whose sum is divisible by k.

Input

First line: n k. Second line: n integers.

Output

The number of such subarrays.

Constraints

Two prefix sums with the same remainder mod k bound a valid subarray. Watch out: in C++/Java, % of a negative number is negative — normalise it.

Example 1

Input

6 5
4 5 0 -2 -3 1

Output

7

Example 2

Input

1 9
5

Output

0

Hints

  1. sum(j+1..i) is divisible by k exactly when prefix[i] and prefix[j] have the same remainder mod k.
  2. Count remainders as you go. Normalise negative remainders: ((x % k) + k) % k.

Approach

Keep cnt[rem] = how many prefix sums so far have remainder rem, starting with cnt[0] = 1 (the empty prefix). For each new prefix remainder m, every earlier prefix with the same remainder ends a valid subarray here, so add cnt[m] and then increment it. In C++/Java, % keeps the sign of the dividend, so fix it with ((p % k) + k) % k.

Complexity: O(n + k) time · O(k) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> cnt(k, 0);
    cnt[0] = 1;
    long long p = 0, ans = 0, x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        p += x;
        int m = ((p % k) + k) % k;
        ans += cnt[m]++;
    }
    cout << ans << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
cnt = [0] * k
cnt[0] = 1
p = ans = 0
for x in a:
    p += x
    m = p % k  # Python's % is never negative for k > 0
    ans += cnt[m]
    cnt[m] += 1
print(ans)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long[] cnt = new long[k];
        cnt[0] = 1;
        long p = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            p += sc.nextLong();
            int m = (int) (((p % k) + k) % k);
            ans += cnt[m]++;
        }
        System.out.println(ans);
    }
}

Solve Subarray Sums Divisible by K online · All practice problems