Easy to understand || gcd || with example and iterations
Intuition\n Describe your first thoughts on how to solve this problem. \n- in outer loop find the gcd of a number with K\n- in inner loop check if the product o
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- in outer loop find the gcd of a number with K\n- in inner loop check if the product of gcd of current number (gcd_num) and gcd of an existing number (gcd_other) in gcd_count is divisible by K\n- if it passes, increase the count\n- increase the frequency of gcd_num in gcd_count, if the gcd_num already exists from any other number its frequency will increase. \n- return the count\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n- Explained with following example : nums = [1,2,3,4,5], k = 2\n\n- Number 1:\n\ngcd(1, 2) = 1\ngcd_num = 1\ngcd_count is empty, so no pairs are found.\nIncrement gcd_count[1] to 1.\ngcd_count becomes {1: 1}.\n\n\n- Number 2:\n\ngcd(2, 2) = 2\ngcd_num = 2\nIterate over gcd_count:\nFor gcd_other = 1, freq = 1:\n(2 * 1) % 2 == 0 is true.\nIncrement count by 1.\ncount becomes 1.\nIncrement gcd_count[2] to 1.\ngcd_count becomes {1: 1, 2: 1}.\n\n- Number 3:\n\ngcd(3, 2) = 1\ngcd_num = 1\nIterate over gcd_count:\nFor gcd_other = 1, freq = 1:\n(1 * 1) % 2 == 0 is false.\nFor gcd_other = 2, freq = 1:\n(1 * 2) % 2 == 0 is true.\nIncrement count by 1.\ncount becomes 2.\nIncrement gcd_count[1] to 2.\ngcd_count becomes {1: 2, 2: 1}.\n\n- Number 4:\n\ngcd(4, 2) = 2\ngcd_num = 2\nIterate over gcd_count:\nFor gcd_other = 1, freq = 2:\n(2 * 1) % 2 == 0 is true.\nIncrement count by 2.\nFor gcd_other = 2, freq = 1:\n(2 * 2) % 2 == 0 is true.\nIncrement count by 1.\ncount becomes 5.\nIncrement gcd_count[2] to 2.\ngcd_count becomes {1: 2, 2: 2}.\n\n- Number 5:\n\ngcd(5, 2) = 1\ngcd_num = 1\nIterate over gcd_count:\nFor gcd_other = 1, freq = 2:\n(1 * 1) % 2 == 0 is false.\nFor gcd_other = 2, freq = 2:\n(1 * 2) % 2 == 0 is true.\nIncrement count by 2.\ncount becomes 7.\nIncrement gcd_count[1] to 3.\ngcd_count becomes {1: 3, 2: 2}.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        unordered_map<int, int> gcd_count;\n        long long count = 0;\n\n        for(int num : nums){\n            int gcd_num = gcd(num, k);\n            \n            for(const auto&[gcd_other, freq] : gcd_count){\n                if((long long)gcd_num * gcd_other % k == 0){\n                    count += freq;\n                }\n            }\n            gcd_count[gcd_num]++;\n        }\n\n        return count;\n    }\n};\n```
['C++']