Pairs with Sum Divisible by K
MediumPractice library · +20 XPmathnumber theoryhash map
Given an array of N integers and an integer K, find the number of pairs (i, j) such that 0 <= i < j < N and (A[i] + A[j]) is divisible by K. Note that the indices i and j must be distinct and the order does not matter, so (i, j) is the same pair as (j, i).
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers A[0], A[1], ..., A[N-1], separated by spaces.
Output
Print a single integer representing the count of such pairs.
Constraints
1 <= N <= 200000 1 <= K <= 200000 0 <= A[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 3 1 2 3 4 5
Output
4
Pairs: (1,2), (1,5), (2,4), (4,5). Sums: 3, 6, 6, 9. All divisible by 3. Count = 4.
Example 2
Input
4 4 1 2 3 4
Output
1
Pairs: (1,3), (4,?) No other pairs. Sums: 4. Count = 1.
Hints
Similar problems
- Divisible by Last DigitMedium
- Count Pairs with Equal Digit ProductMedium
- Two Sum Modulo KMedium
- Count Pairs with Digit Sum Divisible by KMedium
- Count Pairs with Sum Divisible by KMedium
- Subarray Sum MultiplesMedium
More topics: Hash Map and Hashing problems, Math and Number Theory problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 3 1 2 3 4 5
Example 2 input
4 4 1 2 3 4