Number of Excellent Pairs

Problem Description

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 both numbers exist in the array and the sum of the number of set bits in num1 OR num2 and num1 AND num2 is greater than or equal to k. Return the number of distinct excellent pairs.

Key Insights

• The pair (num1, num2) must be distinct and can include duplicates of the same number.
• The condition involves bitwise operations which can be computed efficiently.
• We can utilize a set to filter unique numbers and avoid counting duplicates.
• The maximum possible number of set bits we need to consider is limited due to the constraints.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case if we check all pairs, but can be optimized. Space Complexity: O(n) for storing the unique numbers.

Solution

To solve this problem, we can follow these steps:

1. Use a set to keep track of the unique numbers in nums.
2. For each unique number, calculate the number of set bits for all combinations with other unique numbers including itself.
3. Use bitwise operations to calculate num1 OR num2 and num1 AND num2.
4. Count the total set bits and check if it meets the condition with k.
5. Keep track of the number of valid pairs and return the result.

Code Solutions