BinarySearch 0868 Number of K-Divisible Pairs

Problem statement

https://binarysearch.com/problems/Number-of-K-Divisible-Pairs/

Solution

Keep counter of reminders.

Complexity

It is O(n) for time and O(min(k, n)) for space.

Code

class Solution:
    def solve(self, A, k):
        cnt = Counter()
        for x in A:
            cnt[x % k] += 1
        
        ans = 0
        for x in cnt:
            if (2 * x) % k == 0: ans += cnt[x]*(cnt[x] - 1)
            else: ans += cnt[x] * cnt[k - x]

        return ans//2