Number of Excellent Pairs
HardPrompt
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
num1andnum2exist in the arraynums. - The sum of the number of set bits in
num1 OR num2andnum1 AND num2is greater than or equal tok, whereORis the bitwise OR operation andANDis 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 <= 60
Approaches
3 approaches with complexity analysis and trade-offs.
This approach simplifies the problem by first finding all unique numbers in the input array. Then, it iterates through all possible pairs of these unique numbers and checks if they form an excellent pair. The condition for an excellent pair (num1, num2) is countSetBits(num1) + countSetBits(num2) >= k, which is derived from the property countSetBits(a) + countSetBits(b) = countSetBits(a OR b) + countSetBits(a AND b).
Algorithm
- First, simplify the problem by noting that
countSetBits(num1 OR num2) + countSetBits(num1 AND num2)is equivalent tocountSetBits(num1) + countSetBits(num2). The problem then becomes finding pairs(num1, num2)fromnumssuch thatcountSetBits(num1) + countSetBits(num2) >= k. - To handle duplicates and the requirement that numbers must exist in
nums, create aHashSetfrom the input arraynumsto get all unique numbers. - Convert the
HashSetinto aListor an array to allow iteration over the unique numbers. - Initialize a counter for excellent pairs to zero.
- Use a pair of nested loops to iterate through all possible ordered pairs
(num1, num2)of the unique numbers. - For each pair, calculate the number of set bits for
num1andnum2usingInteger.bitCount(). - If the sum of their bit counts is greater than or equal to
k, increment the counter. - After checking all pairs, return the total count.
Walkthrough
First, we address the fact that pairs are formed from numbers present in nums, and duplicates don't add new number choices. We use a HashSet to store the unique elements from the input array nums.
We then convert this set of unique numbers into a list or array to allow indexed access.
The core of the algorithm is a pair of nested loops that iterate through every possible pair (num1, num2) from the list of unique numbers. For each pair, we calculate the number of set bits for both num1 and num2 using a built-in function like Integer.bitCount().
We then check if the sum of these bit counts is greater than or equal to k. If the condition is met, we increment a counter for excellent pairs. Since (a, b) and (b, a) are distinct pairs, the nested loops naturally cover all U * U pairs, where U is the count of unique numbers. Finally, the total count is returned.
import java.util.HashSet;import java.util.Set;import java.util.ArrayList;import java.util.List; class Solution { public long countExcellentPairs(int[] nums, int k) { Set<Integer> uniqueNumsSet = new HashSet<>(); for (int num : nums) { uniqueNumsSet.add(num); } List<Integer> uniqueNums = new ArrayList<>(uniqueNumsSet); long count = 0; for (int num1 : uniqueNums) { for (int num2 : uniqueNums) { if (Integer.bitCount(num1) + Integer.bitCount(num2) >= k) { count++; } } } return count; }}Complexity
Time
O(N + U^2), where `N` is the length of `nums` and `U` is the number of unique elements. It takes `O(N)` to create the set of unique numbers. The nested loops run `U*U` times. In the worst case, `U` can be up to `N`, leading to a time complexity of `O(N^2)`, which is too slow for the given constraints.
Space
O(U), where `U` is the number of unique elements in `nums`. In the worst case, `U` can be equal to `N` (the length of `nums`), making the space complexity `O(N)`.
Trade-offs
Pros
Simple to understand and implement.
Correctly uses the simplified condition for excellent pairs.
Cons
The time complexity is quadratic with respect to the number of unique elements, which is highly inefficient for large inputs.
This approach will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
This approach improves upon the brute-force method by realizing that the actual values of the numbers do not matter, only the count of their set bits. It first calculates the number of set bits for each unique number and then counts how many numbers exist for each possible bit count. Finally, it uses these frequencies to find the number of excellent pairs.
Algorithm
- First, obtain the set of unique numbers from
numsusing aHashSet. - Initialize a frequency array,
bitCountsFreq, of size 32 (since aninthas at most 32 bits) to all zeros. This array will store the count of unique numbers for each possible number of set bits. - Iterate through each unique number, calculate its set bit count using
Integer.bitCount(), and increment the corresponding index in thebitCountsFreqarray. - Initialize a counter
excellentPairsCountto 0. - Use two nested loops, both iterating from
i = 0to 31 andj = 0to 31. These represent the bit counts of the two numbers in a pair. - Inside the loops, if
i + j >= k, it means a number withiset bits and a number withjset bits form an excellent pair. Add the productbitCountsFreq[i] * bitCountsFreq[j]toexcellentPairsCount. - Return
excellentPairsCount.
Walkthrough
The key insight is that the condition countSetBits(num1) + countSetBits(num2) >= k only depends on the bit counts of the numbers, not their actual values.
We start by finding the unique numbers in nums using a HashSet to avoid redundant calculations. We then create a frequency array, say bitCountsFreq, of size 32. bitCountsFreq[i] will store the number of unique elements from nums that have exactly i set bits. We iterate through the unique numbers, calculate the set bit count for each, and update the corresponding frequency in bitCountsFreq.
After populating the frequency array, we can find the total number of excellent pairs. We use two nested loops, both iterating from 0 to 31, representing the possible bit counts b1 and b2. For each pair of bit counts (b1, b2), if b1 + b2 >= k, it means any number with b1 set bits can form an excellent pair with any number with b2 set bits. The number of such pairs is bitCountsFreq[b1] * bitCountsFreq[b2]. We add this product to our total count. The final sum is the total number of distinct excellent pairs.
import java.util.HashSet;import java.util.Set; class Solution { public long countExcellentPairs(int[] nums, int k) { Set<Integer> uniqueNums = new HashSet<>(); for (int num : nums) { uniqueNums.add(num); } long[] bitCountsFreq = new long[32]; for (int num : uniqueNums) { bitCountsFreq[Integer.bitCount(num)]++; } long excellentPairsCount = 0; for (int i = 0; i < 32; i++) { if (bitCountsFreq[i] == 0) continue; for (int j = 0; j < 32; j++) { if (bitCountsFreq[j] == 0) continue; if (i + j >= k) { excellentPairsCount += bitCountsFreq[i] * bitCountsFreq[j]; } } } return excellentPairsCount; }}Complexity
Time
O(N + C^2), where `N` is the length of `nums` and `C` is the maximum number of bits (32). `O(N)` is for processing the input array. The nested loops for counting pairs run `C*C` times, which is a constant `32*32 = 1024`. The overall complexity is dominated by the initial processing, making it `O(N)`.
Space
O(U + C), where `U` is the number of unique elements and `C` is the constant size of the bit count frequency array (32). This simplifies to `O(U)`, which can be `O(N)` in the worst case.
Trade-offs
Pros
Significantly more efficient than the brute-force approach with a linear time complexity.
Handles large inputs within the time limits.
Cons
While the asymptotic time complexity is optimal, the constant factor in the counting part (
32*32operations) can be improved.
This is a further optimization of the frequency counting approach. Instead of using nested loops to sum up the pairs, which takes C*C operations (where C is the bit count limit), we can use a more efficient counting method. For each bit count b1, we need to find the number of partners with bit count b2 such that b2 >= k - b1. This can be found quickly if we pre-calculate suffix sums on the bit count frequency array.
Algorithm
- Get the set of unique numbers from
numsusing aHashSet. - Create a frequency array
bitCountsFreqof size 32 and populate it by iterating through the unique numbers and counting their set bits. - Create a suffix sum array,
suffixSum, of size 33.suffixSum[i]will store the total count of numbers withior more set bits. - Compute the suffix sums by iterating from
i = 31down to 0:suffixSum[i] = suffixSum[i+1] + bitCountsFreq[i]. - Initialize
excellentPairsCountto 0. - Iterate with a single loop for
b1from 0 to 31. - For each
b1withbitCountsFreq[b1] > 0, calculate the minimum required bits for a partner:required_b2 = k - b1. - The number of valid partners is the sum of frequencies for all bit counts from
required_b2upwards, which is readily available insuffixSum[max(0, required_b2)]. - Add
bitCountsFreq[b1] * suffixSum[max(0, required_b2)]toexcellentPairsCount. - Return the total count.
Walkthrough
The initial steps are the same as the previous approach: get unique numbers and populate a frequency array bitCountsFreq for their bit counts.
The optimization lies in the final counting step. For a given bit count b1, we are looking for partners with bit count b2 such that b1 + b2 >= k, which is equivalent to b2 >= k - b1. Instead of iterating through all possible b2 for each b1, we can find the total number of unique numbers whose bit count is at least k - b1 in one go.
To do this efficiently, we pre-compute a suffix sum array, say suffixSum, on bitCountsFreq. suffixSum[i] will store the total count of numbers with i or more set bits (i.e., bitCountsFreq[i] + bitCountsFreq[i+1] + ...). This can be computed in a single pass over the bitCountsFreq array (from right to left).
With the suffixSum array, for each bit count b1 (from 0 to 31), we find the required bit count for its partner: required_b2 = k - b1. The number of unique numbers that can be a valid partner is suffixSum[required_b2]. We then add bitCountsFreq[b1] * suffixSum[required_b2] to our total count. This process is repeated for all b1 from 0 to 31, which takes only a single loop.
import java.util.HashSet;import java.util.Set; class Solution { public long countExcellentPairs(int[] nums, int k) { Set<Integer> uniqueNums = new HashSet<>(); for (int num : nums) { uniqueNums.add(num); } long[] bitCountsFreq = new long[32]; for (int num : uniqueNums) { bitCountsFreq[Integer.bitCount(num)]++; } long[] suffixSum = new long[33]; for (int i = 31; i >= 0; i--) { suffixSum[i] = suffixSum[i+1] + bitCountsFreq[i]; } long excellentPairsCount = 0; for (int i = 0; i < 32; i++) { if (bitCountsFreq[i] > 0) { int required = k - i; if (required < 0) { required = 0; } if (required < 33) { // Ensure index is within bounds of suffixSum excellentPairsCount += bitCountsFreq[i] * suffixSum[required]; } } } return excellentPairsCount; }}Complexity
Time
O(N + C), where `N` is the length of `nums` and `C` is 32. It takes `O(N)` for processing the input, `O(C)` for populating frequencies, `O(C)` for suffix sums, and `O(C)` for the final count. This is `O(N)` overall and is more efficient than the previous approach by a constant factor in the counting part (`C` vs `C*C`).
Space
O(U + C), where `U` is the number of unique elements and `C` is the constant size of the arrays (32). This simplifies to `O(U)`, which can be `O(N)` in the worst case.
Trade-offs
Pros
The most efficient approach with optimal time complexity.
The counting logic is optimized to a single pass after pre-computation, making it faster in practice than the nested loop counting.
Cons
Slightly more complex to implement due to the additional suffix sum array and logic.
Solutions
Solution
class Solution {public long countExcellentPairs(int[] nums, int k) { Set<Integer> s = new HashSet<>(); for (int v : nums) { s.add(v); } 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 {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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.