# 2354. Number of Excellent Pairs

## 题目

——“优质数对的数目

You are given a 0-indexed positive integer array `nums` and a positive integer `k`.

A pair of numbers `(num1, num2)` is called excellent if the following conditions are satisfied:

• Both the numbers `num1` and `num2` exist in the array `nums`.
• The sum of the number of set bits in `num1 OR num2` and `num1 AND num2` is greater than or equal to `k`, where `OR` is the bitwise OR operation and `AND` is the bitwise AND operation.

Return the number of distinct excellent pairs.

Two pairs `(a, b)` and `(c, d)` are considered distinct if either `a != c` or `b != d`. For example, `(1, 2)` and `(2, 1)` are distinct.

Note that a pair `(num1, num2)` such that `num1 == num2` can also be excellent if you have at least one occurrence of `num1` in the array.

Example 1:

```Input: nums = [1,2,3,1], k = 3
Output: 5
Explanation: The excellent pairs are the following:
- (3, 3). (3 AND 3) and (3 OR 3) are both equal to (11) in binary. The total number of set bits is 2 + 2 = 4, which is greater than or equal to k = 3.
- (2, 3) and (3, 2). (2 AND 3) is equal to (10) in binary, and (2 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3.
- (1, 3) and (3, 1). (1 AND 3) is equal to (01) in binary, and (1 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3.
So the number of excellent pairs is 5.```

Example 2:

```Input: nums = [5,1,1], k = 10
Output: 0
Explanation: There are no excellent pairs for this array.
```

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 109`
• `1 <= k <= 60`

## 代码

``````class Solution(object):
def countExcellentPairs(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def hammingWeight(n):
n = ((n & 0xaaaaaaaa) >> 1) + (n & 0x55555555)
n = ((n & 0xcccccccc) >> 2) + (n & 0x33333333)
n = ((n & 0xf0f0f0f0) >> 4) + (n & 0x0f0f0f0f)
n = ((n & 0xff00ff00) >> 8) + (n & 0x00ff00ff)
n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff)
return n
N = 32
cnt = [0] * N
for n in set(nums):
cnt[hammingWeight(n)] += 1
ret = 0
for i in range(N):
for j in range(N):
if i + j >= k:
ret += cnt[i] * cnt[j]
return ret``````

AC，收工。

——此处是内容的分割线——