Number of Excellent Pairs solution and explanation
8 more videos on this problem
Weekly Contest 303 | 2354. Number of Excellent PairscodingMohan · 10:10 · 5K views
Leetcode 2354. Number of Excellent Pairs | Weekly Contest 303. HardCode with Alisha · 29:04 · 2K views
LeetCode 2354. Number of Excellent Pairs | Very Easy | EnglishThinkCode · 10:51 · 1K views
【每日一题】LeetCode 2354. Number of Excellent PairsHuifeng Guan · 22:36 · 997 views
2354. Number of Excellent Pairs (Leetcode Hard)Programming Live with Larry · 59:48 · 589 views
Leetcode Weekly contest 303 - Hard - Number of Excellent PairsPrakhar Agrawal · 10:40 · 522 views
(Hard)Number of Excellent Pairs | Leetcode Weekly 303 - Hitesh TripathiCoding Talkies | Newton School · 16:55 · 226 views
[LeetCode Weekly Contest 303] Number of Excellent PairsSandeep Kumar · 15:18 · 108 views
Leetcode 2354. Number of Excellent Pairs - compute bitsum frequency and do simple countingCode-Yao · 14:56 · 30 views
The problem
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
Approach overview
Problem 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 1: Bit Count and Hashing
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.
from collections import defaultdict
def countExcellentPairs(nums, k):
nums = list(set(nums))
bit_count = defaultdict(int)
for num in nums:
cnt = bin(num).count('1')
bit_count[cnt] += 1
result = 0
for x in bit_count:
for y in bit_count:
if x + y >= k:
result += bit_count[x] * bit_count[y]
return result
# Example usage:
nums = [1, 2, 3, 1]
k = 3
print(countExcellentPairs(nums, k)) # Output: 5import java.util.HashMap;
import java.util.HashSet;
public class ExcellentPairs {
public static int countExcellentPairs(int[] nums, int k) {
HashSet<Integer> uniqueNums = new HashSet<>();
for (int num : nums) {
uniqueNums.add(num);
}
HashMap<Integer, Integer> bitCountMap = new HashMap<>();
for (int num : uniqueNums) {
int count = Integer.bitCount(num);
bitCountMap.put(count, bitCountMap.getOrDefault(count, 0) + 1);
}
int result = 0;
for (int x : bitCountMap.keySet()) {
for (int y : bitCountMap.keySet()) {
if (x + y >= k) {
result += bitCountMap.get(x) * bitCountMap.get(y);
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1};
int k = 3;
System.out.println(countExcellentPairs(nums, k)); // Output: 5
}
}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.
Approach 2: Two Pointer Technique on Sort Order
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.
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <iostream>
int countExcellentPairs(std::vector<int>& nums, int k) {
std::unordered_set<int> uniqueNums(nums.begin(), nums.end());
std::vector<int> bitCounts;
for (int num : uniqueNums) {
bitCounts.push_back(__builtin_popcount(num));
}
std::sort(bitCounts.begin(), bitCounts.end());
int left = 0, right = bitCounts.size() - 1, count = 0;
while (left <= right) {
if (bitCounts[left] + bitCounts[right] >= k) {
count += (right - left + 1);
right--;
} else {
left++;
}
}
return count;
}
int main() {
std::vector<int> nums = {1, 2, 3, 1};
int k = 3;
std::cout << countExcellentPairs(nums, k) << std::endl; // Output: 5
return 0;
}function countExcellentPairs(nums, k) {
let uniqueNums = [...new Set(nums)];
let bitCounts = uniqueNums.map(num => num.toString(2).split('0').join('').length);
bitCounts.sort((a, b) => a - b);
let left = 0, right = bitCounts.length - 1, count = 0;
while (left <= right) {
if (bitCounts[left] + bitCounts[right] >= k) {
count += (right - left + 1);
right--;
} else {
left++;
}
}
return count;
}
// Example usage:
let nums = [1, 2, 3, 1];
let k = 3;
console.log(countExcellentPairs(nums, k)); // Output: 5In 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.
Time Complexity: O(n log n) due to sorting, and Space Complexity: O(n) for storing bit counts.
Approach 3: Default Approach
func countExcellentPairs(nums []int, k int) int64 {
s := map[int]bool{}
for _, v := range nums {
s[v] = true
}
cnt := make([]int, 32)
for v := range s {
t := bits.OnesCount(uint(v))
cnt[t]++
}
ans := 0
for v := range s {
t := bits.OnesCount(uint(v))
for i, x := range cnt {
if t+i >= k {
ans += x
}
}
}
return int64(ans)
}Complexity comparison
| 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. |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Number of Excellent Pairs easy or hard?
LeetCode classifies Number of Excellent Pairs as a Hard problem because the key insight is not obvious. Recognizing that popcount(a | b) + popcount(a & b) simplifies to popcount(a) + popcount(b) allows the problem to be reduced to counting bit-count pairs instead of comparing every number pair.
Number of Excellent Pairs Python/Java solution
In Python or Java, compute popcount using built-in functions such as bin(x).count('1') in Python or Integer.bitCount(x) in Java. Store frequencies of each bit count and iterate over possible pairs whose sum is at least k. This avoids O(n²) comparisons and runs close to O(n).
How to solve Number of Excellent Pairs in O(n)?
Remove duplicates from nums using a set, compute the popcount for each number, and store the frequency of each bit count. Iterate through all bit-count pairs and add freq[a] * freq[b] whenever a + b ≥ k. Since the range of bit counts is constant, the pair enumeration is small and the overall runtime is effectively linear in n.
What is the best approach for Number of Excellent Pairs?
The most efficient approach aggregates numbers by their bit counts and counts valid combinations of bit-count pairs. After removing duplicates, compute popcount for each number and store frequencies. Then count pairs of bit counts whose sum is at least k. This runs in O(n + B²) time where B is the maximum bit count (~30).
Is Number of Excellent Pairs asked at Google/Amazon/Meta?
This problem reflects patterns commonly asked in big tech interviews, especially those involving bit manipulation and pair counting. Similar variations appear in Google and Meta interview prep sets where candidates must reduce pair comparisons using aggregated statistics like bit counts.
What data structure is used in Number of Excellent Pairs?
The core data structures are a set for removing duplicate numbers and a hash map or frequency array to store counts of popcounts. These structures allow efficient aggregation and counting without checking every pair of numbers.
What is the time complexity of Number of Excellent Pairs?
The optimal solution runs in O(n + B²) time after deduplicating the input, where B is the number of possible bit counts (at most 30 for integers). Because B is constant, the algorithm behaves close to O(n) in practice. Space complexity is O(B) for storing bit-count frequencies.