#2354

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Excellent Pairs

Calculate the number of excellent pairs in an array using bit counting, hash sets, and efficient pair scanning techniques.

array hash table binary search bit manipulation

Problem Statement

Given a 0-indexed positive integer array nums and a positive integer k, an excellent pair consists of two numbers where the sum of the set bits in their AND and OR results is at least k. You need to count all distinct excellent pairs.

Return the total number of excellent pairs in nums. Each pair (num1, num2) is considered distinct if num1 and num2 are distinct values from the array. Optimize using the array scanning plus hash lookup pattern to handle large inputs efficiently.

Examples

Example 1

Input: nums = [1,2,3,1], k = 3

Output: 5

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

There are no excellent pairs for this array.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 60

Solution Approach

Deduplicate and Count Set Bits

Remove duplicate numbers from nums and calculate the number of 1 bits in each number using bit manipulation. Store the counts in a hash map or array to allow fast lookup.

Sort and Use Binary Search

Sort the unique set bit counts and for each count, use binary search to find how many counts satisfy the sum with k. This leverages array scanning plus hash lookup to avoid O(n^2) brute force.

Aggregate Excellent Pairs

Sum the counts from the previous step to compute the total number of excellent pairs. Ensure each pair is counted exactly once and handle both (num1, num2) and (num2, num1) properly when required.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting and binary search over unique bit counts, space complexity is O(n) to store counts and hash map entries.

What Interviewers Usually Probe

Look for handling duplicates correctly to prevent overcounting.
Expect candidates to optimize bit counting rather than comparing numbers directly.
Check if the candidate uses array scanning plus hash lookup efficiently for large n.

Common Pitfalls or Variants

Common pitfalls

Failing to deduplicate nums before counting excellent pairs, which inflates results.
Using nested loops on all pairs leading to TLE for large arrays.
Miscounting set bits or misunderstanding the combined AND and OR bit sum condition.

Follow-up variants

Count excellent pairs where only the OR bits count towards k instead of AND plus OR.
Find excellent pairs in a multidimensional array or matrix using similar bit manipulation.
Compute excellent pairs with an added constraint on the difference between numbers.

FAQ

What exactly defines an excellent pair in this problem?

An excellent pair is a pair of numbers from nums where the total number of 1 bits in their AND and OR results is at least k.

Can I use brute force to find excellent pairs?

Brute force is too slow for large arrays; using deduplication, bit counting, and binary search is necessary for efficiency.

How does array scanning plus hash lookup help here?

It allows quick lookup of bit counts and efficient pairing without iterating through all possible combinations.

Do I need to consider the order of numbers in a pair?

Pairs are considered distinct based on values, but both (num1, num2) and (num2, num1) can contribute depending on implementation.

What is the maximum array length this approach handles efficiently?

This pattern efficiently handles arrays up to length 105 using deduplication and binary search over set bit counts.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#2306 naming a company #2411 smallest subarrays with maximum bitwise or #2275 largest combination with bitwise and greater than zero