Count Array Pairs Divisible by K LeetCode solution in Python

1
class Solution:
2
    def countPairs(self, nums: List[int], k: int) -> int:
3
        counter = Counter()  # hashmap dicitionary of python
4
        ans = 0
5
        n = len(nums)
6

7
        for i in range(n):
8
            x = math.gcd(
9
                k, nums[i]
10
            )  # ex: 10 = k and we have nums[i] as 12 so gcd will be 2
11
            want = k // x  # what do we want from upper ex: we need 5
12
            for num in counter:
13
                if (
14
                    num % want == 0
15
                ):  # so if we find a number that is divisible by 5 then we can multiply it to 12 and make it a factor of 10 for ex we find 20 so it will be 240 which is divisible by 10 hence we will add it to answer
16
                    ans += counter[
17
                        num
18
                    ]  # we are adding the freq as we can find no of numbers that have same factor
19
            counter[
20
                x
21
            ] += 1  # here we are increasing the freq of 2 so that if we find 5 next time we can add these to the answer
22
        return ans