Fastest Python Solution using Defaultdict
\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        seen=defaultdict(int)\n        pairs=[]\n        count=0\n        for i in
```\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        seen=defaultdict(int)\n        pairs=[]\n        count=0\n        for i in range(len(nums)):\n            if nums[i] not in seen:\n                seen[nums[i]]=[]\n                seen[nums[i]].append(i)\n            else:\n                for j in seen[nums[i]]:\n                    pairs.append((i,j))\n                seen[nums[i]].append(i)\n        for (i,j) in pairs:\n            if (i*j)%k == 0:\n                count+=1\n        return count\n```\n **Thought Processes **\n \nWhen confronted with an algorithm challenge, we should immediately rule out the use of brute force. If we keep track of the numbers we\xA0see when looping over the list, we\xA0can quickly see if there are any pairs. \n\nFirst we loop through the list to make a dictionary, which\xA0storing\xA0each encourntered\xA0num as the key and a list of its indices\xA0as the value using defaultdict.\xA0\n{\nnum1: [idx1 of num1, idx2 of num1],\nnum2: [idx1 of num2, idx2 of num2, idx3 of num2],\n...\n}\nThe way we make this dictionary is by checking if the newly encountered num is already present in the dictionary.\xA0\nIf no,\xA0we add the num and its index into the dictionary:\xA0\nseen[num]=[]\nseen[num].append[idx of num]\nif yes, we first loop through all the indices of num to generate (i, j) pairs.\xA0\nthen we append the\xA0index of the num\xA0to the dict.\xA0\nseen[num].append[idx of num] \n\ni is the current index we are in, j is the index among seen[num]\nhere is what happens when we loop through the list: \n3:[0]\xA0\n1:[1]\xA0\n2:[2]\xA0\n2:[2,3] => (3,2)\n2:[2,3,4] =>(4,2) (4.3)\n1:[1,5] =>(5,1)\n3[0,6] =>(6,0)\n\nHaving all the i, j pairs ready, we can check if they are divisible by k or not.\xA0\n\nIf you have simpler solutions, let me know!\n\n\n\n
['Python']