Getting everything ready for you…

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

0s

Practice › Hashing & Two Pointers

Pairs Divisible by K

Medium · Hashing & Two Pointers

Count the pairs of indices i < j such that a[i] + a[j] is divisible by k.

Input

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

Output

The number of pairs.

Constraints

Checking every pair is O(n²) — too slow for n = 10^5. The answer can exceed the 32-bit range.

Example 1

Input

5
1 2 3 4 5
3

Output

4

Example 2

Input

3
2 2 2
2

Output

3

Hints

  1. Only the remainders a[i] % k matter: (x + y) % k == 0 exactly when x % k + y % k is 0 or k.
  2. Scan left to right with a count of each remainder seen so far. Element x pairs with every earlier element whose remainder is (k − x % k) % k.

Approach

For each element with remainder r = x % k, a partner needs remainder (k − r) % k. The extra % k makes remainder 0 pair with 0. Walk the array once. First add count[(k − r) % k], the earlier elements that pair with this one, then do count[r]++. Counting before inserting means every pair i < j is counted exactly once. With n = 10^5 the answer can reach about 5 × 10^9, so use a 64-bit counter.

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

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    long long k;
    cin >> k;
    vector<long long> cnt(k, 0);
    long long pairs = 0;
    for (long long x : a) {
        long long r = x % k;
        pairs += cnt[(k - r) % k];
        cnt[r]++;
    }
    cout << pairs << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
cnt = [0] * k
pairs = 0
for x in a:
    r = x % k
    pairs += cnt[(k - r) % k]
    cnt[r] += 1
print(pairs)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        int k = sc.nextInt();
        long[] cnt = new long[k];
        long pairs = 0;
        for (long x : a) {
            int r = (int) (x % k);
            pairs += cnt[(k - r) % k];
            cnt[r]++;
        }
        System.out.println(pairs);
    }
}

Solve Pairs Divisible by K online · All practice problems