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.
This approach relies on calculating the count of set bits (population count) in different integers. By using a hashmap to store counts of numbers with distinct set bits count, we can efficiently compute the number of excellent pairs.
In this implementation, we first eliminate duplicates from the input list. Then, for each unique number, we determine the count of set bits. Using a hashmap, we store the frequency of numbers with a particular set bit count.
Finally, we iterate over the possible pairs of distinct set bit counts to calculate the number of valid excellent pairs that satisfy the constraint by checking if the sum of their bit counts is greater than or equal to k.
Time Complexity: O(n + m^2), where n is the number of elements in nums, and m is the number of unique bit count values. Space complexity is O(m) due to storing bit counts.
This approach involves sorting distinct numbers based on their bit count and using a two-pointer technique to find the number of valid excellent pairs. By sorting the bit counts, potential pairs can be incrementally evaluated for their validity against the given k constraint.
In this C++ implementation, we use the two-pointer technique on the sorted bit count array. By moving pointers based on their sum relative to k, we can efficiently find all valid excellent pairs without recalculating bit counts repeatedly.
C++
JavaScript
Time Complexity: O(n log n) due to sorting, and Space Complexity: O(n) for storing bit counts.
| Approach | Complexity |
|---|---|
| Bit Count and Hashing | Time Complexity: O(n + m^2), where n is the number of elements in nums, and m is the number of unique bit count values. Space complexity is O(m) due to storing bit counts. |
| Two Pointer Technique on Sort Order | Time Complexity: O(n log n) due to sorting, and Space Complexity: O(n) for storing bit counts. |
| 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. |
Weekly Contest 303 | 2354. Number of Excellent Pairs • codingMohan • 4,967 views views
Watch 8 more video solutions →Practice Number of Excellent Pairs with our built-in code editor and test cases.
Practice on FleetCode