Watch 9 video solutions for Number of Excellent Pairs, a hard level problem involving Array, Hash Table, Binary Search. This walkthrough by codingMohan has 4,967 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text 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:
num1 and num2 exist in the array nums.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 <= 1051 <= nums[i] <= 1091 <= k <= 60Problem Overview: You are given an integer array nums and an integer k. A pair (a, b) is considered excellent if popcount(a) + popcount(b) ≥ k, where popcount(x) is the number of set bits in x. The task is to count all ordered pairs formed from distinct values in nums that satisfy this condition.
The key observation comes from bit manipulation: popcount(a | b) + popcount(a & b) = popcount(a) + popcount(b). Because the condition depends only on the number of set bits in each value, the actual numbers do not matter after computing their bit counts. Removing duplicates first simplifies the counting because identical values contribute the same bit count.
Approach 1: Bit Count and Hashing (O(n + B²) time, O(B) space)
Start by inserting all values from nums into a set to remove duplicates. Compute the set-bit count for each number using a built-in popcount operation. Store the frequency of each bit count in a hash map or fixed-size array (maximum 30–31 bits for typical constraints). Once you know how many numbers have each bit count, iterate over every pair of bit counts (c1, c2). If c1 + c2 ≥ k, add freq[c1] * freq[c2] to the answer because any number with c1 bits can pair with any number with c2 bits.
This method avoids comparing individual numbers and instead works with aggregated counts. The constant range of bit counts keeps the nested loop small. It relies heavily on hash tables and bit manipulation.
Approach 2: Two Pointer Technique on Sorted Bit Counts (O(n log n) time, O(n) space)
After removing duplicates, compute the popcount of each number and store the results in an array. Sort this array. Now the problem becomes: count how many ordered pairs of bit counts have a sum ≥ k. Use two pointers on the sorted array. Fix the left pointer at the smallest bit count and move the right pointer from the end. When bits[left] + bits[right] ≥ k, every element between left and right forms a valid pair with right, so add that count and move the right pointer. Otherwise move the left pointer forward.
This approach treats the problem like a classic pair-sum counting task after transformation. Sorting enables efficient scanning with two pointers and avoids the quadratic check across all numbers. The technique is common in array problems involving pair conditions.
Recommended for interviews: The bit-count hashing approach is usually the cleanest explanation. It shows that you recognized the popcount identity and reduced the problem from numbers to bit-count frequencies. Mentioning the brute-force pair check first demonstrates understanding, but moving to aggregated counting shows algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Count and Hashing | O(n + B²) | O(B) | Best general solution when bit-count range is small (≤30). Efficient counting using frequency buckets. |
| Two Pointer on Sorted Bit Counts | O(n log n) | O(n) | Useful when transforming the problem into a sorted pair-sum check. Simple to reason about in interviews. |