Count Equal and Divisible Pairs in an Array (Brute Force & Optimal Approach)
IntuitionUsing nested loops and going through all pairs and checking if it is divisible by k or notApproachNested Loop and HashmapComplexity
Time complexity:
O(
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Using nested loops and going through all pairs and checking if it is divisible by k or not

# Approach
<!-- Describe your approach to solving the problem. -->
Nested Loop and Hashmap

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(n2)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(1)

# Code
```cpp []
class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        // Brute Force Approach
        // Time Complexity : O(n2)
        // Space Complexity : O(1)

        // long count=0;
        // for(int i=0;i<nums.size();i++)
        // {
        //     for(int j=i+1;j<nums.size();j++)
        //     {
        //         if(nums[i]==nums[j] && (i*j)%k==0)
        //         {
        //             count++;
        //         }
        //     }
        // }
        // return count;

        //Optimal Approach
        // Time Complexity : O(n2)
        // Space Complexity : O(n)

        unordered_map<int,vector<int>>map;
        for(int i=0;i<nums.size();i++)
        {
            map[nums[i]].push_back(i);
        }
        long count=0;
        for(auto val:map)
        {
            vector<int>index = val.second;
            for(int i=0;i<index.size();i++)
            {
                for(int j=i+1;j<index.size();j++)
                {
                    if((index[i]*index[j])%k==0)
                    {
                        count++;
                    }
                }
            }
        }
        return count;
    }
};
```
['C++']