Explanation with diagram | C++ code | Set theory
Let\u2019s say \nn(A) denotes the number of set bits in \u2018A\u2019.\nn(B) denotes the number of set bits in \u2018B\u2019.\n\nThen n( A & B ) denotes the num
Let\u2019s say \n**n(A)** denotes the number of set bits in **\u2018A\u2019**.\n**n(B)** denotes the number of set bits in **\u2018B\u2019**.\n\nThen **n( A & B )** denotes the number of set bits in **\u2018A&B\u2019**.\nAnd **n( A | B)** denotes the number of set bits in **\u2018A|B\u2019**.\n\nIf we convert this problem to set theory, \nThen it will look like this.\n\n![image](https://assets.leetcode.com/users/images/34825a73-a4f2-461b-b267-700c9864ccda_1658635426.6096902.jpeg)\n\n\n\n**n(A)** \t    will be \u201CBlue+Yellow\u201D\n**n(B)** \t    will be \u201CYellow+Green\u201D\n**n( A&B )**  will be \u201CYellow\u201D\n**n( A|B )**    will be \u201CBlue+Yellow+Green\u201D\n\nNow, what we want is,\n**n( A&B ) + n( A|B ) >=k**\n\n**\u201CYellow\u201D + \u201CBlue+Yellow+Green\u201D >=k**\n\nIt is same as,\n**\u201CBlue + Yellow\u201D + \u201CYellow + Green\u201D>=k**\n\n**n(A) + n(B) >=k**.\n\nSo, our ultimate target is to calculate number of distinct pairs (a,b) where \n(number of set bits of a + number of set bits of b) >=k.\n\n**Step 1:** Maintain one set of given numbers to avoid duplicates.\n**Step 2:** Maintain the frequency array. Where freq[i] denotes the number of elements having i number of set bits.\n**Step 3:** Now we want to calculate the pairs (a,b) such that, n(a) + n(b) >=k\n**Step 4:** For this, iterate over every element of the set(mentioned in Step 1). Let\u2019s say the current number is \u2018curr\u2019, and it is having a \u2018cnt\u2019 number of set bits. A pair (curr,x) is valid, if n(x)>=k-cnt. Now we want to find the number of elements having set bits count greater than (k-cnt). Evaluate it using, freq array.\n\n```\nclass Solution {\npublic:\n    int cntSetBits(int n){\n        int ans=0;\n        // cout<<n<<\' \';\n        while(n){\n            if(n&1){\n                ans++;\n            }\n            n=(n>>1);\n        }\n        // cout<<ans<<\'\\n\';\n        return ans;\n    }\n    long long countExcellentPairs(vector<int>& nums, int k) {\n        long long ans=0;\n        vector<long long>freq(63);\n        set<int>st(nums.begin(),nums.end());\n        for(auto n:st){\n            freq[cntSetBits(n)]++;\n        }\n        for(auto n:st){\n            int my=cntSetBits(n);\n            int least=max(0,k-my);\n            for(int i=least;i<63;i++){\n                ans+=freq[i];\n            }\n        }\n        return ans;\n    }\n};\n```\n
['Bit Manipulation', 'C', 'Ordered Set', 'C++']