✅ C++ || Binary Search in Set Bits of Each Unique Number
Main Logic -\nConsider Two Numbers A and B\nSetbits( A or B) + Setbits( A and B) = Setbits(A) + Setbits(B)\n\nApproach -\n First We will Find the Set Bits of ea
**Main Logic -**\nConsider Two Numbers A and B\n**Setbits( A or B) + Setbits( A and B) = Setbits(A) + Setbits(B)**\n\nApproach -\n* First We will Find the Set Bits of each Unique Number in array and store them in a seperate array\n* We are finding set bits of unique numbers only to avoid duplicate pairs\n* Now sort the array which contain number of setbits of each unique number\n* Now for each set bit x find another set bit y such that x + y >= k so x and y will form a pair  (To find Y we will use binary search)\n* Since array is sorted in ascending order so each element after y will also form pair with x\n* So for x total pairs will be add arr.size() - index of y  add this to the ans\n* Find pairs for each x in array of setbits and add them to the ans\n\n**Complexity**\nTime - O(NlogN)\nSpace - O(N)\n```\nclass Solution {\npublic:\n    long long countExcellentPairs(vector<int>& nums, int k) {\n        int n = nums.size();\n        unordered_map<int, int> mp;\n      \n        for(int i=0; i<n; i++)\n            mp[nums[i]] =  __builtin_popcount(nums[i]);       //store set bits of each unique number in nums[i]\n        \n        vector<int> v;\n        for(auto &x:mp)\n            v.push_back(x.second);                //push set bits or each unique number of nums[i] in a vector\n        sort(v.begin(), v.end());            //sort the vector\n        \n\t\t//Now for each set bit x find a corresponding set bit y such that x + y >= k\n\t\t// if x = v[i] then y = v[i] - k\n\t\t//since the vector is sorted so for each x find y using binary search\n\t\t//now x and y will form a pair but each element after y will also form a pair with x because vector is sorted in ascending order \n\t\t//so if x + y >= k then for each z > y     x +z >= k \n\t\t//so in ans add v.size() - index of y\n\t\t\n        long long ans = 0;\n        for(int i=0; i<v.size(); i++)\n        {\n            auto it = lower_bound(v.begin(), v.end(), k - v[i]);\n            ans += (v.end() - it);\n        }\n        return ans;\n    }\n};\n```\n**Clean Code Without Comments**\n```\nclass Solution {\npublic:\n    long long countExcellentPairs(vector<int>& nums, int k) {\n        int n = nums.size();\n        unordered_map<int, int> mp;\n      \n        for(int i=0; i<n; i++)\n            mp[nums[i]] =  __builtin_popcount(nums[i]);\n\t\t\t\n        vector<int> v;\n        for(auto &x:mp)\n            v.push_back(x.second);\n\t\t\t\n        sort(v.begin(), v.end());\n        long long ans = 0;\n\t\t\n        for(int i=0; i<v.size(); i++)\n        {\n            auto it = lower_bound(v.begin(), v.end(), k - v[i]);\n            ans += (v.end() - it);\n        }\n        return ans;\n    }\n};\n```
['C', 'Binary Tree']