##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2354.html

# 2354. Number of Excellent Pairs

• Difficulty: Hard.
• Related Topics: Array, Hash Table, Binary Search, Bit Manipulation.
• Similar Questions: Two Sum.

## Problem

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

## Solution

• class Solution {
public long countExcellentPairs(int[] nums, int k) {
long[] cnt = new long[30];
long res = 0L;
Set<Integer> set = new HashSet<>();
for (int a : nums) {
}
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;
}
}

############

class Solution {
public long countExcellentPairs(int[] nums, int k) {
Set<Integer> s = new HashSet<>();
for (int v : nums) {
}
long ans = 0;
int[] cnt = new int[32];
for (int v : s) {
int t = Integer.bitCount(v);
++cnt[t];
}
for (int v : s) {
int t = Integer.bitCount(v);
for (int i = 0; i < 32; ++i) {
if (t + i >= k) {
ans += cnt[i];
}
}
}
return ans;
}
}

• class Solution:
def countExcellentPairs(self, nums: List[int], k: int) -> int:
s = set(nums)
ans = 0
cnt = Counter()
for v in s:
cnt[v.bit_count()] += 1
for v in s:
t = v.bit_count()
for i, x in cnt.items():
if t + i >= k:
ans += x
return ans

############

# 2354. Number of Excellent Pairs
# https://leetcode.com/problems/number-of-excellent-pairs/

class Solution:
def countExcellentPairs(self, nums: List[int], k: int) -> int:
nums = set(nums)

MAX = 32
bits = [0] * MAX

for x in nums:
bits[x.bit_count()] += 1

res = 0
for i in range(1, MAX):
for j in range(1, MAX):
if i + j >= k:
res += bits[i] * bits[j]

return res


• class Solution {
public:
long long countExcellentPairs(vector<int>& nums, int k) {
unordered_set<int> s(nums.begin(), nums.end());
vector<int> cnt(32);
for (int v : s) ++cnt[__builtin_popcount(v)];
long long ans = 0;
for (int v : s) {
int t = __builtin_popcount(v);
for (int i = 0; i < 32; ++i) {
if (t + i >= k) {
ans += cnt[i];
}
}
}
return ans;
}
};

• func countExcellentPairs(nums []int, k int) int64 {
s := map[int]bool{}
for _, v := range nums {
s[v] = true
}
cnt := make([]int, 32)
for v := range s {
t := bits.OnesCount(uint(v))
cnt[t]++
}
ans := 0
for v := range s {
t := bits.OnesCount(uint(v))
for i, x := range cnt {
if t+i >= k {
ans += x
}
}
}
return int64(ans)
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).
The text passage contains a problem statement for a programming challenge, including examples and a solution in multiple programming languages. The problem involves finding the number of distinct excellent pairs in an array based on bitwise operations and set bit counts.
no_question

the passage does not contain a direct mathematical question or a word problem that requires a numerical answer. instead, it provides a problem statement and a solution for a programming challenge. the examples given are part of the problem description and are not standalone questions.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2354.html

# 2354. Number of Excellent Pairs

• Difficulty: Hard.
• Related Topics: Array, Hash Table, Binary Search, Bit Manipulation.
• Similar Questions: Two Sum.

## Problem

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

## Solution

• class Solution {
public long countExcellentPairs(int[] nums, int k) {
long[] cnt = new long[30];
long res = 0L;
Set<Integer> set = new HashSet<>();
for (int a : nums) {
}
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;
}
}

############

class Solution {
public long countExcellentPairs(int[] nums, int k) {
Set<Integer> s = new HashSet<>();
for (int v : nums) {
}
long ans = 0;
int[] cnt = new int[32];
for (int v : s) {
int t = Integer.bitCount(v);
++cnt[t];
}
for (int v : s) {
int t = Integer.bitCount(v);
for (int i = 0; i < 32; ++i) {
if (t + i >= k) {
ans += cnt[i];
}
}
}
return ans;
}
}

• class Solution:
def countExcellentPairs(self, nums: List[int], k: int) -> int:
s = set(nums)
ans = 0
cnt = Counter()
for v in s:
cnt[v.bit_count()] += 1
for v in s:
t = v.bit_count()
for i, x in cnt.items():
if t + i >= k:
ans += x
return ans

############

# 2354. Number of Excellent Pairs
# https://leetcode.com/problems/number-of-excellent-pairs/

class Solution:
def countExcellentPairs(self, nums: List[int], k: int) -> int:
nums = set(nums)

MAX = 32
bits = [0] * MAX

for x in nums:
bits[x.bit_count()] += 1

res = 0
for i in range(1, MAX):
for j in range(1, MAX):
if i + j >= k:
res += bits[i] * bits[j]

return res


• class Solution {
public:
long long countExcellentPairs(vector<int>& nums, int k) {
unordered_set<int> s(nums.begin(), nums.end());
vector<int> cnt(32);
for (int v : s) ++cnt[__builtin_popcount(v)];
long long ans = 0;
for (int v : s) {
int t = __builtin_popcount(v);
for (int i = 0; i < 32; ++i) {
if (t + i >= k) {
ans += cnt[i];
}
}
}
return ans;
}
};

• func countExcellentPairs(nums []int, k int) int64 {
s := map[int]bool{}
for _, v := range nums {
s[v] = true
}
cnt := make([]int, 32)
for v := range s {
t := bits.OnesCount(uint(v))
cnt[t]++
}
ans := 0
for v := range s {
t := bits.OnesCount(uint(v))
for i, x := range cnt {
if t+i >= k {
ans += x
}
}
}
return int64(ans)
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).
user
The text passage contains a problem statement for a programming challenge, including examples and a solution in multiple programming languages. The problem involves finding the number of distinct excellent pairs in an array based on bitwise operations and set bit counts.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question or a word problem that requires a numerical answer. Instead, it provides a problem statement and a solution for a programming challenge. The examples given are part of the problem description and are not standalone questions.