Basic example
Input
arr = [1, 2, 3, 4], k = 2
Output
2
Remainders are [1,0,1,0]. There are two pairs with the same remainder: indices (0,2) and (1,3).
Full lesson preview
Count pairs with the same remainder
Count unordered pairs of array elements whose remainders modulo k are equal using hashing.
Python practice30 minHashing & SetsAdvancedLast updated March 26, 2026
Problem statement
Given an array of integers arr and a positive integer k, return the number of unordered pairs (i, j) with 0 <= i < j < len(arr) such that arr[i] % k == arr[j] % k. Use a hash map (dictionary) to count frequencies of remainders and compute the number of pairs efficiently.
Task
Use a frequency map of remainders to count pairs in O(n) time.
Examples
Input format
Function input: count_pairs_same_remainder(arr, k) where arr is a list of integers and k is a positive integer.
Output format
Return an integer: the number of unordered pairs with equal remainder modulo k.
Constraints
0 <= len(arr) <= 10^5, -10^9 <= arr[i] <= 10^9, 1 <= k <= 10^9. Expected O(n) time and O(min(n,k)) extra space.
Samples
Sample 1
Input
arr = [5, 17, 9, 13, 1], k = 6
Output
2
Remainders: [5,5,3,1,1]. Pairs: two remainders 5 -> 1 pair, two remainders 1 -> 1 pair, total 2.