Count Pairs with Same Remainder
MediumPractice library · +20 XPhash mapcountingmodulo arithmetic
Given an array of N integers and an integer K, find the number of pairs (i, j) such that 0 <= i < j < N and the elements A[i] and A[j] have the same remainder when divided by K. That is, A[i] % K == A[j] % K.
Input
The first line contains two integers N and K, separated by a space. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer representing the total 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
2
Remainders mod 3 are: 1, 2, 0, 1, 2. Pairs with same remainder: (1,4) mod 3 is 1; (2,5) mod 3 is 2. Total 2 pairs.
Example 2
Input
6 4 8 12 10 4 16 20
Output
10
Remainders mod 4 are: 0, 0, 2, 0, 0, 0. Pairs with remainder 0: (8,12), (8,4), (8,16), (8,20), (12,4), (12,16), (12,20), (4,16), (4,20), (16,20). Total 10 pairs.
Hints
# 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
6 4 8 12 10 4 16 20