c++ prefix sum solution O(n)
C++\nclass Solution {\npublic:\n    long long countExcellentPairs(vector<int>& A, int k) {\n        unordered_map<int, int> pcnt;\n        vector<int> psum(66);
```C++\nclass Solution {\npublic:\n    long long countExcellentPairs(vector<int>& A, int k) {\n        unordered_map<int, int> pcnt;\n        vector<int> psum(66);\n        for(auto& a : A) pcnt[a] = __builtin_popcount(a);\n        for(auto [_,v] : pcnt) psum[v] += 1;\n        for(int i = 1; i < 66; i++) psum[i] += psum[i-1];\n\n        long long res = 0;\n        for(auto [me, cnt] : pcnt) {\n            res += psum.back() - psum[max(k-cnt-1,0)];\n        }\n\n        return res;\n    }\n};\n```
[]