Binary Search || O(NlogN) solution using bit manipulation
First of all, remove the duplicates from the array, since we only want unique answers. We can use map or set to get unique elements. There is a property that th
First of all, remove the duplicates from the array, since we only want unique answers. We can use map or set to get unique elements. There is a property that the sum of the number of set bits in ```num1 | num2``` and ```num1 & num2``` is equal to the set bits in the sum of the two number.\nFor example: if num1 = 4, num2 = 8 then the set bits in ```num1 | num2``` is 2 and set bits in ```num1 & num2``` is 0. The sum of the number num1 and num2, ```12``` also contains 2 + 0 set bits.\nWe can use this property to solve the question optimally.\n\n Now, we make another array which contains set bits of the numbers. \n If the given array was ```[1,2,3,1,536870911]```, then we can make another array ```[1,1,2,29]```. Now we will operate on this array only. We first sort the array. Then we can use binary search to find the lower bound of (k - nums[i]) to find the number of possible answer for that index. Below is the code.\n \n ```\n class Solution {\npublic:\n\t// Function to find number of set bits in a number\n    int setBits(int n) {\n        int count = 0;\n        while (n) {\n            count += n & 1;\n            n >>= 1;\n        }\n        return count;\n    }\n    long long countExcellentPairs(vector<int>& nums, int k) {\n        unordered_map<int,int> mp;\n        for(int i=0;i<nums.size();i++) {\n            mp[nums[i]] = 1;\n        }\n        vector<int> realNums; // new array which contains set bits\n        for(auto &it: mp) {\n            realNums.push_back(setBits(it.first)); // store set bits\n        }\n        sort(realNums.begin(), realNums.end()); // sort the array to perform binary search\n        long long ans = 0;\n        for(int i=0;i<realNums.size();i++) {\n            int curr = realNums[i];\n\t\t\t   int target = k - curr;\n            int j = lower_bound(realNums.begin() + i, realNums.end(), target) - realNums.begin(); // find target in the right part of the array, we will not consider left part.\n            long long total = realNums.size() - j; // total numbers lying on right part satisfying the condition\n           // If the same number also satisfy the condition then we dont want to consider it twice\n\t\t\t   if(j == i) { \n\t\t\t\t\tans++;\n\t\t\t\t\tif(total-1) {\n\t\t\t\t\t\tans += 2 * (total-1);\n\t\t\t\t\t}\n\t\t\t\t} \n            else {\n                ans += 2*total; // (num1,num2) and (num2,num1) both possibility\n            }\n        }\n        return ans;\n    }\n};\n ```
['Bit Manipulation', 'Binary Tree', 'C++']