# Number of Excellent Pairs
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-excellent-pairs)
Canonical: https://scaleengineer.com/dsa/problems/number-of-excellent-pairs
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute Force on Unique Numbers
This approach simplifies the problem by first finding all unique numbers in the input array. Then, it iterates through all possible pairs of these unique numbers and checks if they form an excellent pair. The condition for an excellent pair `(num1, num2)` is `countSetBits(num1) + countSetBits(num2) >= k`, which is derived from the property `countSetBits(a) + countSetBits(b) = countSetBits(a OR b) + countSetBits(a AND b)`.
**Time:** O(N + U^2), where `N` is the length of `nums` and `U` is the number of unique elements. It takes `O(N)` to create the set of unique numbers. The nested loops run `U*U` times. In the worst case, `U` can be up to `N`, leading to a time complexity of `O(N^2)`, which is too slow for the given constraints. · **Space:** O(U), where `U` is the number of unique elements in `nums`. In the worst case, `U` can be equal to `N` (the length of `nums`), making the space complexity `O(N)`.
**Pros:** Simple to understand and implement.; Correctly uses the simplified condition for excellent pairs.
**Cons:** The time complexity is quadratic with respect to the number of unique elements, which is highly inefficient for large inputs.; This approach will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
First, we address the fact that pairs are formed from numbers present in `nums`, and duplicates don't add new number choices. We use a `HashSet` to store the unique elements from the input array `nums`.

We then convert this set of unique numbers into a list or array to allow indexed access.

The core of the algorithm is a pair of nested loops that iterate through every possible pair `(num1, num2)` from the list of unique numbers. For each pair, we calculate the number of set bits for both `num1` and `num2` using a built-in function like `Integer.bitCount()`.

We then check if the sum of these bit counts is greater than or equal to `k`. If the condition is met, we increment a counter for excellent pairs. Since `(a, b)` and `(b, a)` are distinct pairs, the nested loops naturally cover all `U * U` pairs, where `U` is the count of unique numbers. Finally, the total count is returned.

```java
import java.util.HashSet;
import java.util.Set;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public long countExcellentPairs(int[] nums, int k) {
        Set<Integer> uniqueNumsSet = new HashSet<>();
        for (int num : nums) {
            uniqueNumsSet.add(num);
        }
        
        List<Integer> uniqueNums = new ArrayList<>(uniqueNumsSet);
        long count = 0;
        
        for (int num1 : uniqueNums) {
            for (int num2 : uniqueNums) {
                if (Integer.bitCount(num1) + Integer.bitCount(num2) >= k) {
                    count++;
                }
            }
        }
        
        return count;
    }
}
```
### Algorithm
*   First, simplify the problem by noting that `countSetBits(num1 OR num2) + countSetBits(num1 AND num2)` is equivalent to `countSetBits(num1) + countSetBits(num2)`. The problem then becomes finding pairs `(num1, num2)` from `nums` such that `countSetBits(num1) + countSetBits(num2) >= k`.
*   To handle duplicates and the requirement that numbers must exist in `nums`, create a `HashSet` from the input array `nums` to get all unique numbers.
*   Convert the `HashSet` into a `List` or an array to allow iteration over the unique numbers.
*   Initialize a counter for excellent pairs to zero.
*   Use a pair of nested loops to iterate through all possible ordered pairs `(num1, num2)` of the unique numbers.
*   For each pair, calculate the number of set bits for `num1` and `num2` using `Integer.bitCount()`.
*   If the sum of their bit counts is greater than or equal to `k`, increment the counter.
*   After checking all pairs, return the total count.

## Counting Bit Frequencies with Nested Loops
This approach improves upon the brute-force method by realizing that the actual values of the numbers do not matter, only the count of their set bits. It first calculates the number of set bits for each unique number and then counts how many numbers exist for each possible bit count. Finally, it uses these frequencies to find the number of excellent pairs.
**Time:** O(N + C^2), where `N` is the length of `nums` and `C` is the maximum number of bits (32). `O(N)` is for processing the input array. The nested loops for counting pairs run `C*C` times, which is a constant `32*32 = 1024`. The overall complexity is dominated by the initial processing, making it `O(N)`. · **Space:** O(U + C), where `U` is the number of unique elements and `C` is the constant size of the bit count frequency array (32). This simplifies to `O(U)`, which can be `O(N)` in the worst case.
**Pros:** Significantly more efficient than the brute-force approach with a linear time complexity.; Handles large inputs within the time limits.
**Cons:** While the asymptotic time complexity is optimal, the constant factor in the counting part (`32*32` operations) can be improved.
### Explanation
The key insight is that the condition `countSetBits(num1) + countSetBits(num2) >= k` only depends on the bit counts of the numbers, not their actual values. 

We start by finding the unique numbers in `nums` using a `HashSet` to avoid redundant calculations. We then create a frequency array, say `bitCountsFreq`, of size 32. `bitCountsFreq[i]` will store the number of unique elements from `nums` that have exactly `i` set bits. We iterate through the unique numbers, calculate the set bit count for each, and update the corresponding frequency in `bitCountsFreq`.

After populating the frequency array, we can find the total number of excellent pairs. We use two nested loops, both iterating from 0 to 31, representing the possible bit counts `b1` and `b2`. For each pair of bit counts `(b1, b2)`, if `b1 + b2 >= k`, it means any number with `b1` set bits can form an excellent pair with any number with `b2` set bits. The number of such pairs is `bitCountsFreq[b1] * bitCountsFreq[b2]`. We add this product to our total count. The final sum is the total number of distinct excellent pairs.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long countExcellentPairs(int[] nums, int k) {
        Set<Integer> uniqueNums = new HashSet<>();
        for (int num : nums) {
            uniqueNums.add(num);
        }
        
        long[] bitCountsFreq = new long[32];
        for (int num : uniqueNums) {
            bitCountsFreq[Integer.bitCount(num)]++;
        }
        
        long excellentPairsCount = 0;
        for (int i = 0; i < 32; i++) {
            if (bitCountsFreq[i] == 0) continue;
            for (int j = 0; j < 32; j++) {
                if (bitCountsFreq[j] == 0) continue;
                if (i + j >= k) {
                    excellentPairsCount += bitCountsFreq[i] * bitCountsFreq[j];
                }
            }
        }
        
        return excellentPairsCount;
    }
}
```
### Algorithm
*   First, obtain the set of unique numbers from `nums` using a `HashSet`.
*   Initialize a frequency array, `bitCountsFreq`, of size 32 (since an `int` has at most 32 bits) to all zeros. This array will store the count of unique numbers for each possible number of set bits.
*   Iterate through each unique number, calculate its set bit count using `Integer.bitCount()`, and increment the corresponding index in the `bitCountsFreq` array.
*   Initialize a counter `excellentPairsCount` to 0.
*   Use two nested loops, both iterating from `i = 0` to 31 and `j = 0` to 31. These represent the bit counts of the two numbers in a pair.
*   Inside the loops, if `i + j >= k`, it means a number with `i` set bits and a number with `j` set bits form an excellent pair. Add the product `bitCountsFreq[i] * bitCountsFreq[j]` to `excellentPairsCount`.
*   Return `excellentPairsCount`.

## Optimized Counting with Suffix Sums
This is a further optimization of the frequency counting approach. Instead of using nested loops to sum up the pairs, which takes `C*C` operations (where `C` is the bit count limit), we can use a more efficient counting method. For each bit count `b1`, we need to find the number of partners with bit count `b2` such that `b2 >= k - b1`. This can be found quickly if we pre-calculate suffix sums on the bit count frequency array.
**Time:** O(N + C), where `N` is the length of `nums` and `C` is 32. It takes `O(N)` for processing the input, `O(C)` for populating frequencies, `O(C)` for suffix sums, and `O(C)` for the final count. This is `O(N)` overall and is more efficient than the previous approach by a constant factor in the counting part (`C` vs `C*C`). · **Space:** O(U + C), where `U` is the number of unique elements and `C` is the constant size of the arrays (32). This simplifies to `O(U)`, which can be `O(N)` in the worst case.
**Pros:** The most efficient approach with optimal time complexity.; The counting logic is optimized to a single pass after pre-computation, making it faster in practice than the nested loop counting.
**Cons:** Slightly more complex to implement due to the additional suffix sum array and logic.
### Explanation
The initial steps are the same as the previous approach: get unique numbers and populate a frequency array `bitCountsFreq` for their bit counts.

The optimization lies in the final counting step. For a given bit count `b1`, we are looking for partners with bit count `b2` such that `b1 + b2 >= k`, which is equivalent to `b2 >= k - b1`. Instead of iterating through all possible `b2` for each `b1`, we can find the total number of unique numbers whose bit count is at least `k - b1` in one go.

To do this efficiently, we pre-compute a suffix sum array, say `suffixSum`, on `bitCountsFreq`. `suffixSum[i]` will store the total count of numbers with `i` or more set bits (i.e., `bitCountsFreq[i] + bitCountsFreq[i+1] + ...`). This can be computed in a single pass over the `bitCountsFreq` array (from right to left).

With the `suffixSum` array, for each bit count `b1` (from 0 to 31), we find the required bit count for its partner: `required_b2 = k - b1`. The number of unique numbers that can be a valid partner is `suffixSum[required_b2]`. We then add `bitCountsFreq[b1] * suffixSum[required_b2]` to our total count. This process is repeated for all `b1` from 0 to 31, which takes only a single loop.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long countExcellentPairs(int[] nums, int k) {
        Set<Integer> uniqueNums = new HashSet<>();
        for (int num : nums) {
            uniqueNums.add(num);
        }
        
        long[] bitCountsFreq = new long[32];
        for (int num : uniqueNums) {
            bitCountsFreq[Integer.bitCount(num)]++;
        }
        
        long[] suffixSum = new long[33];
        for (int i = 31; i >= 0; i--) {
            suffixSum[i] = suffixSum[i+1] + bitCountsFreq[i];
        }
        
        long excellentPairsCount = 0;
        for (int i = 0; i < 32; i++) {
            if (bitCountsFreq[i] > 0) {
                int required = k - i;
                if (required < 0) {
                    required = 0;
                }
                if (required < 33) { // Ensure index is within bounds of suffixSum
                    excellentPairsCount += bitCountsFreq[i] * suffixSum[required];
                }
            }
        }
        
        return excellentPairsCount;
    }
}
```
### Algorithm
*   Get the set of unique numbers from `nums` using a `HashSet`.
*   Create a frequency array `bitCountsFreq` of size 32 and populate it by iterating through the unique numbers and counting their set bits.
*   Create a suffix sum array, `suffixSum`, of size 33. `suffixSum[i]` will store the total count of numbers with `i` or more set bits.
*   Compute the suffix sums by iterating from `i = 31` down to 0: `suffixSum[i] = suffixSum[i+1] + bitCountsFreq[i]`.
*   Initialize `excellentPairsCount` to 0.
*   Iterate with a single loop for `b1` from 0 to 31.
*   For each `b1` with `bitCountsFreq[b1] > 0`, calculate the minimum required bits for a partner: `required_b2 = k - b1`.
*   The number of valid partners is the sum of frequencies for all bit counts from `required_b2` upwards, which is readily available in `suffixSum[max(0, required_b2)]`.
*   Add `bitCountsFreq[b1] * suffixSum[max(0, required_b2)]` to `excellentPairsCount`.
*   Return the total count.

# Solutions
### Java

```java
class Solution {
public
  long countExcellentPairs(int[] nums, int k) {
    Set<Integer> s = new HashSet<>();
    for (int v : nums) {
      s.add(v);
    }
    long ans = 0;
    int[] cnt = new int[32];
    for (int v : s) {
      int t = Integer.bitCount(v);
      ++cnt[t];
    }
    for (int v : s) {
      int t = Integer.bitCount(v);
      for (int i = 0; i < 32; ++i) {
        if (t + i >= k) {
          ans += cnt[i];
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countExcellentPairs(vector<int> &nums, int k) {
    unordered_set<int> s(nums.begin(), nums.end());
    vector<int> cnt(32);
    for (int v : s)
      ++cnt[__builtin_popcount(v)];
    long long ans = 0;
    for (int v : s) {
      int t = __builtin_popcount(v);
      for (int i = 0; i < 32; ++i) {
        if (t + i >= k) {
          ans += cnt[i];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int: s = set(nums) ans = 0 cnt = Counter() for v in s: cnt[v . bit_count()] += 1 for v in s: t = v . bit_count() for i, x in cnt . items(): if t + i >= k: ans += x return ans

```