To solve Number of Excellent Pairs, first deduplicate nums and count set bits for each number. Then use a sorted array or hash map to efficiently find pairs whose combined set bits meet or exceed k. This approach avoids brute force O(n^2) checks and leverages array scanning plus hash lookup for fast performance.
Problem Statement
Given a 0-indexed positive integer array nums and a positive integer k, an excellent pair consists of two numbers where the sum of the set bits in their AND and OR results is at least k. You need to count all distinct excellent pairs.
Return the total number of excellent pairs in nums. Each pair (num1, num2) is considered distinct if num1 and num2 are distinct values from the array. Optimize using the array scanning plus hash lookup pattern to handle large inputs efficiently.
Examples
Example 1
Input: nums = [1,2,3,1], k = 3
Output: 5
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
There are no excellent pairs for this array.
Constraints
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 109
- 1 <= k <= 60
Solution Approach
Deduplicate and Count Set Bits
Remove duplicate numbers from nums and calculate the number of 1 bits in each number using bit manipulation. Store the counts in a hash map or array to allow fast lookup.
Sort and Use Binary Search
Sort the unique set bit counts and for each count, use binary search to find how many counts satisfy the sum with k. This leverages array scanning plus hash lookup to avoid O(n^2) brute force.
Aggregate Excellent Pairs
Sum the counts from the previous step to compute the total number of excellent pairs. Ensure each pair is counted exactly once and handle both (num1, num2) and (num2, num1) properly when required.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n log n) due to sorting and binary search over unique bit counts, space complexity is O(n) to store counts and hash map entries.
What Interviewers Usually Probe
- Look for handling duplicates correctly to prevent overcounting.
- Expect candidates to optimize bit counting rather than comparing numbers directly.
- Check if the candidate uses array scanning plus hash lookup efficiently for large n.
Common Pitfalls or Variants
Common pitfalls
- Failing to deduplicate nums before counting excellent pairs, which inflates results.
- Using nested loops on all pairs leading to TLE for large arrays.
- Miscounting set bits or misunderstanding the combined AND and OR bit sum condition.
Follow-up variants
- Count excellent pairs where only the OR bits count towards k instead of AND plus OR.
- Find excellent pairs in a multidimensional array or matrix using similar bit manipulation.
- Compute excellent pairs with an added constraint on the difference between numbers.
How GhostInterview Helps
- Automatically deduplicates nums and calculates bit counts, avoiding manual preprocessing errors.
- Highlights array scanning plus hash lookup optimizations to reduce time complexity.
- Tracks edge cases like zero excellent pairs or high k values to guide correct solution paths.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What exactly defines an excellent pair in this problem?
An excellent pair is a pair of numbers from nums where the total number of 1 bits in their AND and OR results is at least k.
Can I use brute force to find excellent pairs?
Brute force is too slow for large arrays; using deduplication, bit counting, and binary search is necessary for efficiency.
How does array scanning plus hash lookup help here?
It allows quick lookup of bit counts and efficient pairing without iterating through all possible combinations.
Do I need to consider the order of numbers in a pair?
Pairs are considered distinct based on values, but both (num1, num2) and (num2, num1) can contribute depending on implementation.
What is the maximum array length this approach handles efficiently?
This pattern efficiently handles arrays up to length 105 using deduplication and binary search over set bit counts.
Need direct help with Number of Excellent Pairs instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Excellent Pairs from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
The "Naming a Company" problem requires determining the number of valid distinct company names from a list of name ideas by swapping prefixes and suffixes.
Open problem page#2411 Smallest Subarrays With Maximum Bitwise ORFind the smallest subarrays with the maximum bitwise OR for each starting index in an array.
Open problem page#2275 Largest Combination With Bitwise AND Greater Than ZeroFind the largest group of integers in an array whose bitwise AND is greater than zero using array scanning and hash lookup.
Open problem page