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.
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; }}Video 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.