Count Pairs Divisible by K
MediumArrayHash TableMathCounting
Description
Given a non-negative integer array nums and a positive integer k, return the number of ordered pairs (i, j) with i < j such that (nums[i] + nums[j]) is divisible by k.
Examples
Input:
nums = [1,2,3,4,5], k = 3Output:
4Explanation:
Pairs (sums divisible by 3): (1,2)=3, (1,5)=6, (2,4)=6, (4,5)=9.
Input:
nums = [4,4,4,4], k = 4Output:
6Explanation:
All C(4,2) = 6 pairs sum to 8, divisible by 4.
Input:
nums = [1,1,1], k = 2Output:
3Explanation:
All three pairs sum to 2, divisible by 2.
Input:
nums = [7], k = 7Output:
0Explanation:
Need at least 2 elements to form a pair.
Constraints
- •
1 ≤ nums.length ≤ 10⁵ - •
0 ≤ nums[i] ≤ 10⁹ - •
1 ≤ k ≤ 10⁵