Modular Pairs Problem

Modular Pairs Problem — ExecCode Medium DSA Practice

Solve the Modular Pairs problem on ExecCode. Free online medium DSA practice in Two Pointers. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Count the pairs of indexes (i, j) with i < j whose values sum to a multiple of k. Each pair of indexes is counted once. Return the number of valid pairs. Use a 64-bit integer. You are given: a — the integers k — the modulus Return the number of pairs. Indexes are 0-based and every index may be used. A pair is valid when (a[i] + a[j]) mod k is 0.

Examples

Input {'a': [1, 2, 3, 4, 5], 'k': 3}; Output 4. Input {'a': [1, 4, 2, 3], 'k': 5}; Output 2. Input {'a': [1, 2, 3, 4, 5], 'k': 2}; Output 4

Constraints

1 <= n <= 1e5 where n = a.length 1 <= k <= 1e5 0 <= a[i] <= 1e9 i < j The count can be large, so use a 64-bit integer Checking every pair is O(n^2) and will Time Limit Exceed

Practice Modular Pairs free on ExecCode. Browse DSA problems, topic map, and placement guides.