Number of Excellent Pairs LeetCode solution in C++

1
class Solution {
2
 public:
3
  typedef long long ll;
4
  int setbits(int n) {
5
    int cnt = 0;
6
    while (n) {
7
      cnt += (n % 2);
8
      n /= 2;
9
    }
10
    return cnt;
11
  }
12

13
  long long countExcellentPairs(vector<int> &nums, int k) {
14
    unordered_set<int> s(nums.begin(), nums.end());
15
    vector<int> v;
16
    for (auto &i : s) {
17
      int x = setbits(i);
18
      v.push_back(x);
19
    }
20
    sort(v.begin(), v.end());
21

22
    ll ans = 0;
23
    for (int i = 0; i < v.size(); i++) {
24
      auto it = lower_bound(v.begin(), v.end(), k - v[i]);
25
      ans += (v.end() - it);
26
    }
27
    return ans;
28
  }
29
};