Number of Excellent Pairs — Solution in Python, Java & C++
Number of Excellent Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Excellent Pairs is a hard coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Binary Search, Bit Manipulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of positive integers and a positive integer k. A pair of numbers (num1, num2) is excellent when:
- both
num1andnum2occur innums, and - the number of set bits in
num1 OR num2plus the number of set bits innum1 AND num2is at leastk.
Pairs are ordered and compared by value: (a, b) and (b, a) are different pairs when a != b, while repeated occurrences of the same values give the same pair. num1 and num2 may be the same value, as long as it occurs at least once.
Return the number of distinct excellent pairs.
CodeKairo bound: the original allows 10^5 elements, whose answer needs 64 bits; here nums.length <= 4 * 10^4, so the answer fits a 32-bit integer.
Example 1
Input: nums = [5,1,6,5], k = 4
Output: 4
Explanation: 5 and 6 each have 2 set bits. The pairs (5,5), (5,6), (6,5) and (6,6) reach 4; any pair with 1 reaches at most 3.
Example 2
Input: nums = [7,8], k = 5
Output: 1
Explanation: Only (7,7): 3 + 3 = 6.
Example 3
Input: nums = [3], k = 10
Output: 0
Constraints
1 <= nums.length <= 4 * 10^41 <= nums[i] <= 10^91 <= k <= 60
Hints for Number of Excellent Pairs
Hint 1
Count the bits of
a OR band ofa AND bbit by bit: what is their sum in terms ofaandbalone?Hint 2
A bit set in both counts twice, a bit set in one counts once — so the sum is
popcount(a) + popcount(b).Hint 3
Deduplicate
nums, bucket the distinct values by popcount (at most 30 buckets), and addcnt[i] * cnt[j]for everyi + j >= k.
How to solve Number of Excellent Pairs
popcount(a OR b) + popcount(a AND b) = popcount(a) + popcount(b), so a pair is excellent based only on the two popcounts, and the counting collapses to at most 30 × 30 bucket pairs.
Approach
- Remove duplicate values from
nums. - Count the distinct values by popcount:
cnt[p]forpfrom 0 to 30. - Sum
cnt[i] * cnt[j]over alli, jwithi + j >= kand return it.
Why it works
Look at one bit. If it is set in both numbers it contributes 1 to the OR and 1 to the AND; if set in exactly one it contributes 1 to the OR only; otherwise nothing. That is exactly its contribution to popcount(a) + popcount(b). Ordered pairs of distinct values (a, b) with popcounts (i, j) number cnt[i] * cnt[j], including a = b when i = j.
Complexity
- Time —
O(n + 30²) - Space —
O(n)
Pitfalls
- Deduplicate first — pairs are counted by value, not by index.
- Pairs are ordered, so
(a, b)and(b, a)are both counted, and(a, a)counts once. - In languages with 32-bit ints, accumulate the sum in a 64-bit variable even though the tightened answer fits.
Reference solution
Python
from typing import List
def countExcellentPairs(nums: List[int], k: int) -> int:
cnt = [0] * 32
for v in set(nums):
cnt[bin(v).count("1")] += 1
total = 0
for i in range(32):
for j in range(32):
if i + j >= k:
total += cnt[i] * cnt[j]
return totalJava
public static int countExcellentPairs(int[] nums, int k) {
long[] cnt = new long[32];
Set<Integer> seen = new HashSet<>();
for (int v : nums) if (seen.add(v)) cnt[Integer.bitCount(v)]++;
long total = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < 32; j++) {
if (i + j >= k) total += cnt[i] * cnt[j];
}
}
return (int) total;
}C++
int countExcellentPairs(vector<int>& nums, int k) {
vector<long long> cnt(32, 0);
unordered_set<int> seen(nums.begin(), nums.end());
for (int v : seen) cnt[__builtin_popcount(v)]++;
long long total = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < 32; j++) {
if (i + j >= k) total += cnt[i] * cnt[j];
}
}
return (int) total;
}JavaScript
var countExcellentPairs = function(nums, k) {
var cnt = new Array(32).fill(0);
var seen = new Set(nums);
seen.forEach(function(v) {
var c = 0;
while (v) { c += v & 1; v >>>= 1; }
cnt[c]++;
});
var total = 0;
for (var i = 0; i < 32; i++) {
for (var j = 0; j < 32; j++) {
if (i + j >= k) total += cnt[i] * cnt[j];
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets