[Java/C++/Python] Inclusion-Exclusion Principle
Intuition\nThe Inclusion-Exclusion Principle\nbits(num1 OR num2) + bits(num1 AND num2) = bits(num1) + bits(num2)\n\n\n# Explanation\nFor all different a in nums
# **Intuition**\nThe Inclusion-Exclusion Principle\n`bits(num1 OR num2) + bits(num1 AND num2) = bits(num1) + bits(num2)`\n<br>\n\n# **Explanation**\nFor all different `a` in `nums`,\ncounts its number of `bits`.\n\nEnumearte the number of bits `k1` and `k2`,\nif `k1 + k2 >= k`,\nwe accumulate `count[k1] * count[k2]`.\n<br>\n\n# **Complexity**\nTime `O(nlogn)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public long countExcellentPairs(int[] A, int k) {\n        long cnt[] = new long[30], res = 0;\n        Set<Integer> set = new HashSet<>();\n        for (int a : A)\n            set.add(a);\n        for (int a : set)\n            cnt[Integer.bitCount(a)]++;\n        for (int i = 1; i < 30; ++i)\n            for (int j = 1; j < 30; ++j)\n                if (i + j >= k)\n                    res += cnt[i] * cnt[j];\n        return res;\n    }\n```\n**C++**\nimproved from @votrubac\n```c++\n    long long countExcellentPairs(vector<int>& A, int k) {\n        long long cnt[30] = {}, res = 0;\n        for (int a : unordered_set<int>(begin(A), end(A)))\n            ++cnt[__builtin_popcount(a)];\n        for (int i = 1; i < 30; ++i)\n            for (int j = 1; j < 30; ++j)\n                if (i + j >= k)\n                    res += cnt[i] * cnt[j];\n        return res;\n    }\n```\n**Python3**\n```py\n    def countExcellentPairs(self, A: List[int], k: int) -> int:\n        c = Counter(map(int.bit_count, set(A)))\n        return sum(c[k1] * c[k2] for k1 in c for k2 in c if k1 + k2 >= k)\n```\n\n
['C', 'Python', 'Java']