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 numbers
num1andnum2exist in the arraynums. - The sum of the number of set bits in
num1 OR num2andnum1 AND num2is greater than or equal tok, whereORis the bitwise OR operation andANDis 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 = 3Output
5The excellent pairs are (3, 3), (2, 3), (3, 2), (1, 3), and (3, 1), so the count is 5.
Example 2
Input
nums = [5,1,1], k = 10Output
0There are no excellent pairs for this array.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= 60