Two Sum Modulo K
MediumPractice library · +20 XPmathhashingnumber theory
Given a list of N integers A and an integer K, find the number of pairs (i, j) such that i < j and (A[i] + A[j]) % K == 0.
Print the total count of such pairs.
Input
The first line contains two integers N and K. The second line contains N integers A_1, A_2, ..., A_N.
Output
Print a single integer: the count of pairs (i, j) with i < j and (A[i] + A[j]) % K == 0.
Constraints
1 <= N <= 200000 1 <= K <= 200000 0 <= A[i] <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 3 1 2 3 4 5
Output
4
Pairs are (1, 2), (1, 5), (2, 4), (4, 5). Sums are 3, 6, 6, 9. All divisible by 3. Count = 4.
Example 2
Input
6 4 1 2 3 4 5 6
Output
3
Pairs are (1, 3), (2, 6), (3, 5), (4, ?), (5, ?). Remainders mod 4: [1, 2, 3, 0, 1, 2]. Pairs summing to multiple of 4: (1,3), (2,6), (3,5). Count = 3.
Hints
Similar problems
- Count Pairs with Equal Digit ProductMedium
- Pairs with Sum Divisible by KMedium
- Count Distinct Prefix SumsMedium
- Divisible by Last DigitMedium
- Count Pairs with Equal Digit SumMedium
- Count Pairs with Digit Sum Divisible by KMedium
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
6 4 1 2 3 4 5 6