Easy C++ Solution || WITH APPROACH EXPLAINED IN DETAIL
\n# Approach\nFirst Thought is that how to reduce the calculation of OR and AND of 2 number repeatedly. We know the inclusion exclusion formula for two numbers\
\n# Approach\nFirst Thought is that how to reduce the calculation of OR and AND of 2 number repeatedly. We know the inclusion exclusion formula for two numbers\nf(a OR b) = f(a) + f(b) - f(a AND b)\n\nLet f(x) be defined as set bits in number x. Then we can write the same formula for the above case.\nf(a OR b) + f(a AND b) = f(a) + f(b)\nSo this means sum of set bits in OR and AND of 2 numbers is same as sum of setbits of those 2 numbers only So no need of OR and AND operations.\n\nAs we have to find distinct pairs so we will store all numbers in set data structure. We will also keep a vector which will keep count of setbits of numbers in set.\n\nFinally if we get the setbits now OUR PROBLEM GOT REDUCED TO finding number of distinct pairs of numbers in array whose sum is >=k. Its simple, we will sort the array and use two pointer technique.\nAs (1,3) and (3,1) are distinct (as given in question) so we will multiply our ans by 2 as we count in array.\n\nBUT THERE IS A CATCH. They are counting (a,a) as a pair too. So we have to keep a track of this too. As it will result in only a single such pair so we will add that in our countsetbits function only.\nLike if (2*setbits_in_nums[i]>=k) then ans++.\n\n# Complexity\n- Time complexity:\nO(NlogN). As we are sorting the array.\n\n- Space complexity:\nO(N). As we are using set data structure.\n\n# Code\n```\nclass Solution {\npublic:\n\n    int countsetbits(int num, long long &ans, int k){\n        int set1= 0;\n        for(int i =0;i<32;i++)\n        {\n            if((1<<i)&num)\n                set1++;\n        }\n        if(2*set1>=k) ans++;\n        return set1;\n    }\n\n    long long countExcellentPairs(vector<int>& nums, int k) {\n        long long ans=0;\n        unordered_set<int> s(nums.begin(), nums.end());\n        vector<int> setbits; \n        for(auto it: s){\n           int bits=countsetbits(it,ans,k);\n           setbits.push_back(bits);\n        }\n\n        sort(setbits.begin(), setbits.end());\n        int start=0;\n        int end=setbits.size()-1;\n        while(start<end){\n            if(setbits[start]+setbits[end]>=k){\n                ans+=(end-start)*2;\n                end--;\n            }\n            else{\n                start++;\n            }\n        }\n\n        return ans;\n    }\n};\n\n```
['Array', 'Hash Table', 'Bit Manipulation', 'Sorting', 'C++']