(–TypeScript–) Explained with 2 Loops and Hash Map
Intuition\n\nThe first solution that comes to mind is to use two loops; one inner loop and one outer loop so that for each element nums[i] we will compute all t
# Intuition\n\nThe first solution that comes to mind is to use two loops; one inner loop and one outer loop so that for each element `nums[i]` we will compute all the products with the aid of the inner loop so that we can check if `nums[i] * nums[j] % k === 0`.\n\nOf course, this approach will take $$O(n^2)$$ time and we can do slightly better.\n\n# Approach\n\n## Math Logic\n\nWe start from the idea that any integer that will be divisible by `k`, that is: `integer % k === 0`, will need to contain `k` a certain amount of times equal to the quotient of the division operation.\n\nThis integer is the product of `nums[i]` and `nums[j]`.\n\nIf the integer or product is composed by `nums[i]` and `nums[j]` that means that `k` will be found in both of `nums[i]` and `nums[j]` and united together as the whole `k` only when we calculate `nums[i] * nums[j]`.\n\nIn other words, `k` is composed from or found in both `nums[i]` and `nums[j]`. When we calculate `nums[i] * nums[j]` the result(product) will contain the entire `k`.\n\n> One more thing to add: it will contain the entire `k` only if the product of `nums[i]` and `nums[j]` is divisible by `k`.\n\nTo decompose an integer we calculate its prime factors. For example, let\'s take the integer `10` and `8`:\n\nThe prime factors of `10` are:\n`10 = 2 * 5`\n\nThe prime factors of `8` are:\n`8 = 2 * 2 * 2 = 2^3` \n\nWhen we lay out the prime factors like this, we can have a look at both of the numbers and select the greatest common divisor, which in the case of `8` and `10` is `2`. This means that the largest number that divides both `8` and `10` is `2`.\n\n## Code Logic\n\nWe will calculate the greatest common divisor of `k` and each number in the `nums` array, like so: \n\n```typescript\nfunction gcd(a: number, b: number){\n    if (b === 0) return a;\n    else return gcd(b, a % b);    \n}\n```\n\nThen we will add each *gcd* to a map where we will incremet the *gcd* value when we find the same *gcd* again.\n\nAt the same time we have a smaller loop which grows as our algorithm progresses, which checks if the `currentGcd` multiplied by all the previous ones and divided by `k` equals `0`. If it does, we increment the `pairs` value with the value of how many times we had the same *gcd* previously.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nfunction countPairs(nums: number[], k: number): number {\n    const gcdCount = new Map<number, number>();\n    let pairs = 0;\n\n    for(let num of nums) {\n        const currentGcd = gcd(num, k);\n        for(let [storedGcd, count] of gcdCount){\n            if((currentGcd * storedGcd) % k === 0){\n                pairs += count;\n            }\n        }\n        gcdCount.set(currentGcd, gcdCount.get(currentGcd) + 1 || 1);\n    }\n    return pairs;\n};\n\nfunction gcd(a: number, b: number){\n    if (b === 0) return a;\n    else return gcd(b, a % b);    \n}\n```
['Array', 'Math', 'Number Theory', 'TypeScript']