C++ Logic explained with pictures
The key to this solution lies in the fact that for any two numbers a and b, the sum of number of set bits in (a AND b) and (a OR b) = sum of number of set bits 
The key to this solution lies in the fact that for any two numbers a and b, the sum of number of set bits in (a AND b) and (a OR b) = sum of number of set bits in a and b individually.\n\nBut why is this true? If we look closely at how AND and OR operations work, we can find out.\n\nConsider a number A which has x set bits in its binary representation and a number B which has y set bits in its binary representation. Also suppose that at k places the set bits of A and B coincide.\n\n![image](https://assets.leetcode.com/users/images/c038def1-371b-4af4-bf1a-f47b2738fe7e_1659461999.0725431.png)\n\nNow if we take A OR B, the number of set bits in the answer will be (x+y-k). This is because in the OR operation, if either of the bits is 1, the resultant bit at that position is also set. This means that for A, there will be a contribution of x set bits to the result and from B, a contibution of y set bits. But the places where the set bits of A and B coincide must\'ve been counted twice in the result as they will produce only one set bit in the answer. Hence, to accomodate this we subtract k from (x+y).\n\n![image](https://assets.leetcode.com/users/images/c24d7aab-3a81-4ab5-a029-f8603cecc336_1659462034.1279852.png)\n\nFor AND operation, the number of set bits in the answer will simply be k as this the number of bits where both the bits in A as well as B are 1.\n\n![image](https://assets.leetcode.com/users/images/ad71bed0-2de9-4126-a4c2-697fe211cc7a_1659462050.6592577.png)\n\nHence, sum of the number of set bits in (A OR B) and (A AND B)  = x+y-k+k = x+y = sum of set bits in A and B.\n\nNow, this problem simply reduces to finding the number of distinct pairs such that the sum of number of set bits in both the number is >= k.\n\nIf we just had to find the number of distinct pairs where the sum is equal to k, we could have used a hashmap, but we also need to find the pairs where the sum is greater than k. \n\nWe can utilise the fact that any number in the given input range will have at most 32 bits. So if we have an array where we count how many numbers in the array have *i* bits set in their binary representation, where 0 <= i <= 31, then we can easily calculate the number of distinct pairs whose sum of set bits is >= k by looping through this array twice, and just with a complexity of O(32 * 32). Also, we need to make sure we keep a count of only distinct numbers in this array as we need to form distinct pairs. We can use a set for this.\n\n```cpp\nclass Solution {\npublic:\n    int count_bits(int num)\n    {  \n        int sum = 0;\n         \n        for(int i=0;i<32;i++)\n        {\n            sum += (((1<<i)&num)!=0); \n        }\n        \n        return sum;   \n    }\n    long long countExcellentPairs(vector<int>& nums, int k)\n    {\n        \n        long long int ans = 0;\n    \n        vector<int>bit_freq(32,0);\n        set<int>distinct;\n        \n        for(int i=0;i<nums.size();i++)\n        {\n            if(distinct.find(nums[i])==distinct.end())\n            {  \n                distinct.insert(nums[i]);\n                int set_bits = count_bits(nums[i]);\n                bit_freq[set_bits]++;\n            }\n        }\n        \n        for(int first=0;first<32;first++)\n        {\n            for(int second=0;second<32;second++)\n            {\n                if(first+second>=k)\n                {\n                    ans += (1ll*bit_freq[first]*bit_freq[second]);\n                }  \n            }\n        }\n        \n        return ans;\n    }\n};\n```\n\n**Complexity Analysis**\n\n- Time Complexity: O(32 * n + 32 * 32). Here, n is the size of the given array. We iterate over the array once and to find the number of set bits we iterate over each number\'s 32 bits. After that we have two nested for loops over the bit frequency array which accounts for the term 32 * 32.\n- Space Complexity: O(n + 32). We use a set to keep track of the distinct elements in the array which takes O(n) space and an array for bit frequency of length 32 which takes O(32) space.
['Bit Manipulation', 'C']