Skip to main content
Talentd

Number of Excellent Pairs - Solution & Explanation

HardArrayHash TableBinary SearchBit Manipulation9 min readAsked at: Epifi
Practice this problem

Problem Statement

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 num1 and num2 exist in the array nums.
  • The sum of the number of set bits in num1 OR num2 and num1 AND num2 is greater than or equal to k, where OR is the bitwise OR operation and AND is 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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= 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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

In 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.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, and Space Complexity: O(n) for storing bit counts.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bit Count and HashingO(n + B²)O(B)Best general solution when bit-count range is small (≤30). Efficient counting using frequency buckets.
Two Pointer on Sorted Bit CountsO(n log n)O(n)Useful when transforming the problem into a sorted pair-sum check. Simple to reason about in interviews.

Video Solution

Weekly Contest 303 | 2354. Number of Excellent Pairs • codingMohan • 5,258 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Number of Excellent Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum