[Leetcode] 2176. Count Equal and Divisible Pairs in an Array

https://leetcode.com/problems/count-equal-and-divisible-pairs-in-an-array/description/?envType=daily-question&envId=2025-04-17

initial

There is a very obvious to find if 2 indexes multiply to have no remainder when divided by k with n^2 solution. But n^2 is crap in interviews so I tried thinking of using hashmap to get indexes quickly with o(1) and I also thought of gcd which is corrrect thinking. But i didnt know how to utilise this except making combinations of all indexes stored as a list value in our hashmap to see if each combination multiplies to be divided by k or not

solution

Actually we dont need each combi. We can store a count variable to see how many times the gcd has been seen before. As we iterate through the rest of the indexes (there is a little trick here that u dont input the index first but after ur logic so that u can iterate through the indexes), if gcd_first * gcd_stored_in_hashmap %k ==0, then we increment our ans by the count variable.

Btw that trick to iterate through the rest of the indexes is

        for i,lst in dic.items():
            hola=defaultdict(int)
            for ele in lst:
                gcd_first = gcd(ele,k)
                for gcd_stored, count in hola.items():
                    if (gcd_first * gcd_stored) %k==0:
                        ans+=count
                hola[gcd_first]+=1

See as we iter through the indexes in the lst, we calc gcd_first. But the inner for loop doesnt run cuz hola is empty. So we just increment the hola's gcd_first key by 1. So effectively the next element in lst can compare with the previous ele in lst cuz now it is stored in hola hashmap.

Also notice why do we ans+= count? So count stores how many times this gcd_value is previously seen before. If the current gcd this stored_gcd_value_in_hashmap % k==0, then effectively we are not explictily calculating each combination 1 by 1 and seeing if it is divisible by k, but since we know how many valid cases there are by multiplying gcd_stored_in_hashmap gcd_current, we can just append that result to answer straight away.

    def countPairs(self, nums: List[int], k: int) -> int:
        dic=defaultdict(list)
        for i,v in enumerate(nums):
            dic[v].append(i)
        ans = 0

        for i,lst in dic.items():
            hola=defaultdict(int)
            for ele in lst:
                gcd_first = gcd(ele,k)
                for gcd_stored, count in hola.items():
                    if (gcd_first * gcd_stored) %k==0:
                        ans+=count
                hola[gcd_first]+=1
        return ans

complexity

Time Complexity:

• Outer loop (iterating through unique numbers): In the worst case, all numbers in nums could be unique. Let U be the number of unique elements in nums. This loop runs U times.
• Inner loop (iterating through indices of a number): For each unique number, the inner loop iterates through all its occurrences. Let count(num) be the number of times num appears in nums. The sum of count(num) over all unique numbers is n (the length of nums).
• Innermost loop (iterating through gcd_counts): In the worst case, gcd_counts could potentially store up to k distinct GCD values (since the GCD of an index and k will be between 1 and k).
• gcd() function: The time complexity of the gcd() function (using the Euclidean algorithm) is O(log(min(a, b))), where a and b are the inputs. In our case, it's O(log(min(index, k))).
• Overall: Combining these, the worst-case time complexity can be roughly estimated as O(n k log(k)). However, the number of unique GCDs encountered for each number's indices might be much smaller than k in practice. A more precise analysis would be complex and depend on the distribution of indices and the value of k.

Space Complexity:

• num_to_indices: This dictionary stores at most n indices in total (across all unique numbers). In the worst case (all numbers are unique), it would store n key-value pairs. So, the space complexity is O(n).
• gcd_counts: This dictionary, within the inner loop, stores the counts of GCDs encountered for the indices of the current number. In the worst case, it can store up to k entries. However, this dictionary is reset for each unique number. The maximum size it reaches at any point is O(k).
• result: This is a single integer, so its space complexity is O(1).

Therefore, the overall space complexity is dominated by num_to_indices, which is O(n).

In summary:

• Time Complexity: Roughly O(n k log(k)) in the worst case, but often better in practice.
• Space Complexity: O(n) due to the storage of indices in num_to_indices.