{x}
blog image

Number of Excellent Pairs

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

Solution Explanation

This problem asks us to find the number of distinct excellent pairs in a given array nums, where a pair (num1, num2) is excellent if:

  1. Both num1 and num2 are in nums.
  2. The sum of set bits in num1 | num2 (bitwise OR) and num1 & num2 (bitwise AND) is greater than or equal to k.

The most efficient approach involves leveraging bit manipulation and hash tables (or sets) to optimize the search for excellent pairs. Here's a breakdown of the solution:

1. Optimization using Set:

First, we use a set (or HashSet in Java, unordered_set in C++) to store the unique numbers from the input array nums. This eliminates redundant calculations since we only need to consider unique numbers.

2. Counting Set Bits:

For each unique number in the set, we calculate the number of set bits (1s in the binary representation) using built-in functions:

  • Python: v.bit_count()
  • Java: Integer.bitCount(v)
  • C++: __builtin_popcount(v)
  • Go: bits.OnesCount(uint(v))

We then store the counts of numbers with a specific number of set bits in a frequency array cnt (or a Counter in Python).

3. Counting Excellent Pairs:

We iterate through the unique numbers again. For each number v, we iterate through the cnt array. For each count cnt[i], representing the number of elements with i set bits, we check if the sum of set bits in v and a number with i set bits is greater than or equal to k. If it is, we add cnt[i] to the total count of excellent pairs ans. This accounts for all possible pairings with numbers having i set bits.

4. Time Complexity Analysis:

  • Creating the set of unique numbers: O(n), where n is the length of nums.
  • Counting set bits and storing frequencies: O(n) in the worst case (all numbers are unique) as bit_count is O(1) on average in most implementations.
  • Iterating through unique numbers and checking pairs: O(n * m) where n is the number of unique numbers and m is the maximum number of set bits (which is 32 in our case as we consider 32-bit integers). In practice m is usually much less than 32 due to constraints. Although this looks like O(n^2), the constant is small, and n can be much smaller than the original size of nums.

Therefore, the overall time complexity is approximately O(n*m) which is close to linear considering m is a relatively small constant.

5. Space Complexity Analysis:

  • The set of unique numbers: O(n) in the worst case (all numbers unique).
  • The frequency array cnt: O(m), where m is the maximum number of set bits (32).

Therefore, the overall space complexity is O(n + m), which is linear with respect to the input size.

In summary: The solution efficiently utilizes bit manipulation and data structures to solve the problem with near-linear time and space complexity. The use of a set reduces redundant computations, and the frequency array cnt speeds up pair counting.