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.

Description Hints 2 Solution Video 10:10

2354. Number of Excellent Pairs

Hard49.7% acceptance1 company

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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 60

Asked at 1 company

Epifi

Topics

Hints open one at a time

Hint 1

Can you find a different way to describe the second condition?

Hint 2

The sum of the number of set bits in (num1 OR num2) and (num1 AND num2) is equal to the sum of the number of set bits in num1 and num2.

10:10

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution