From raw thoughts to a solution | O(NlogN) time
What we need \nWe need to find distinct pairs of (a, b) from nums such that set bit in a&b and set bits in a|b is >= k\n\nRaw thought on a and b\nThink in a way
**What we need** \nWe need to find distinct pairs of (a, b) from nums such that set bit in a&b and set bits in a|b is >= k\n\n**Raw thought on a and b**\nThink in a way that what is contribution of a set bit from a or from b to this sum that is needed >= k.\nA bit can contribute a plus one in a&b operation else it will definately contribute a plus in a|b.\nAssume two numbers in binary:\n\t00001111  -> a\n\t11110000 -> b\n\t\n\ta&b = 00000000 \n\ta|b = 11111111\n\nIf somewhere a\'s bit is at at position i, and b\'s bit is not set, then a will not contribute in a&b but will contribute in sum a plus one in a|b. Now, the other case would if a\'s i-th bit is set and b\'s i-th bit is also set then total contribution in sum would be plus 2, i.e. one from a&b and one from a|b, we can say that a will contribute a plus one and b will contribute a plus one in sum. So, if a bit is set in a number it will definately contribute a plus one in sum of number of bits in a&b and a|b.\n\nTotal sum required is >= k. If a contributes i bits (assuming a has i set bits), then b must contribute atleast (k - i) therefore b must have k - i set bits, can have greater than too as we need total sum >= k.\nI have made a bits vector that denotes numbers of unique values in nums having i bits set. As we need a b for an a such that it has >= (k - i) set bits, hence I have also done a prefix sum backwards.\n\nHere\'s the code :\n\n```\nclass Solution {\npublic:\n    long long countExcellentPairs(vector<int>& nums, int k) {\n        vector <long long> bits(65, 0);\n        unordered_map <int, int> mp;\n        for(auto &num : nums){\n            mp[num]++;\n            if(mp[num] == 1){\n                //saving uniques values in nums according to set bits in bits vector\n                bits[__builtin_popcount(num)]++;\n            } \n        }\n        \n        \n        for(int i = 63; i>=0; i--){\n            bits[i] += bits[i+1];\n        }\n        \n        long long ans = 0;\n        \n        //iterating for number of set bits in a\n        for(int i = 0; i<=64; i++){\n            int setbitsInb = (k - i >= 0 ? k - i : 0);\n            long long NumOfb = bits[setbitsInb], NumOfa = (i != 64 ? bits[i] - bits[i+1] : bits[i]);\n            ans += (NumOfa*NumOfb);\n            \n        }\n \n        return ans;\n    }\n};\n```\n\n\n
['Bit Manipulation', 'Prefix Sum']