Simple | Two Pointers | C++ | O(nlogn) time | O(n) space
Problem asks the number of pairs such that set bits(num1 and num2) + set bits(num1 or num2) must be >=k.\n\nObservations:\nOne simple observation is that\nset_b
Problem asks the number of pairs such that set bits(num1 and num2) + set bits(num1 or num2) must be >=k.\n\n**Observations:**\nOne simple observation is that\n**set_bits(num1 and num2) + set_bits(num1 or num2) is equal to set_bits(num1)+set_bits(num2) .**\n\nWe store each element\'s set bits count and element itself in a set so as to have unique pairs and also sorted pairs in order of their set bits count.\n\nwe copy the set to the vector so that we can perform two pointers method to count desired pairs.\n\n**Working:**\nNow answer of how two pointers method works \n\nex. test case: nums = [1,2,3,1], k = 3\nPairs stored in vector: [{1,1},{1,2},{2,3}]\ntaking p=0 and q=vector_size -1\n\nNow if(v[p].first+v[q].first>=k) \ntaking q as a element of pair we can easily consider all indexes which are >=p to make pair with index q so ans=ans+2*(q-p).\nMultiplied by 2  as for example (1,3) and (3,1) would count as 2 pairs.\n \nAlso one case  is that when q makes pair with itself so if v[q].first*2>=k then ans=ans+1.\n\n**Complexity:**\nTime complexity: O(nlogn)\nspace complexity: O(n)\n\n**C++ Code:**\n```\nlong long countExcellentPairs(vector<int>& nums, int k) {\n        long long ans=0;\n        // initializing a set to only have unique pairs \n        // first element in a pair of set represent number of set bits \n        // second element in a pair of set represent number of number itself \n        set <pair<int,int>> s;\n        \n\t\t//__builtin_popcount(int x) is a method used to count number of set bits in integer x\n        for(int i=0;i<nums.size();i++){\n            s.insert({__builtin_popcount(nums[i]),nums[i]});\n        }\n        \n        // now coping the set to vector so that we can take 2 pointers \n        vector <pair<int,int>> v;\n        for(auto it:s){\n            v.push_back(it);\n        }\n        \n        int p=0,q=v.size()-1;\n        // ans stores the number of pairs\n        while(p<=q){\n            if(v[p].first+v[q].first>=k){\n                if(2*v[q].first>=k){\n                    ans++;\n                }\n                ans+=2*(q-p);\n                q--;\n            }\n            else{\n                p++;\n            }\n        }\n        return ans;\n    }\n```\n
['Two Pointers', 'C']