304 North Cardinal St.
Dorchester Center, MA 02124

# Number of Excellent Pairs LeetCode Solution

## Problem – Number of Excellent Pairs LeetCode Solution

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`

### Number of Excellent Pairs LeetCode Solution in Java

``````    public long countExcellentPairs(int[] A, int k) {
long cnt[] = new long, res = 0;
Set<Integer> set = new HashSet<>();
for (int a : A)
for (int a : set)
cnt[Integer.bitCount(a)]++;
for (int i = 1; i < 30; ++i)
for (int j = 1; j < 30; ++j)
if (i + j >= k)
res += cnt[i] * cnt[j];
return res;
}
``````

### Number of Excellent Pairs LeetCode Solution in C++

``````    long long countExcellentPairs(vector<int>& A, int k) {
long long cnt = {}, res = 0;
for (int a : unordered_set<int>(begin(A), end(A)))
++cnt[__builtin_popcount(a)];
for (int i = 1; i < 30; ++i)
for (int j = 1; j < 30; ++j)
if (i + j >= k)
res += cnt[i] * cnt[j];
return res;
}
``````

### Number of Excellent Pairs LeetCode Solution in Python

``````class Solution:
def countExcellentPairs(self, A: List[int], k: int) -> int:
# Count number of bits in (n) in binary
def numOfBits(n):
ans = 0
while n:
ans += (n & 1)
n >>= 1
return ans

# Sort the number of bits of each distinct number from A
B = sorted([numOfBits(a) for a in set(A)])

# Right pointer start at n - 1.
n, j, ans = len(B), len(B) - 1, 0

for i in range(n):
# If the starting i, j don't meet the condition, continue for the next i.
if B[i] + B[j] < k:
continue

# Move until j = 0 or B[i] + B[j] < k
while j >= 1 and B[i] + B[j - 1] >= k:
j -= 1

# All the number to the right of the pointer j (inclusive) make no less
# sum of bits with B[i]
ans += n - j

return ans
``````
##### Number of Excellent Pairs LeetCode Solution Review:

In our experience, we suggest you solve this Number of Excellent Pairs LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Number of Excellent Pairs LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Number of Excellent Pairs LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions