#2354
Number of Excellent Pairs
candidate master · 1455 · lc hard +32 · verified · 49% accepted · 620 likes · top 35%
Description
You are given a 0-indexed array of positive integers nums and a positive integer k.
Call a pair (num1, num2) excellent when:
- Both num1 and num2 appear in nums.
- The total set-bit count of num1 OR num2 plus the set-bit count of num1 AND num2 is at least k.
Count and return the number of distinct excellent pairs.
Pairs (a, b) and (c, d) are distinct when a != c or b != d. For instance, (1, 2) and (2, 1) are distinct.
A pair where both values are equal is valid if that value appears at least once in nums.
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.
Code
1
2
3