Problem Description

You have an array of positive integers nums and a positive integer k. Your task is to count pairs of numbers from the array that meet a special condition called "excellent."

A pair (num1, num2) is considered excellent if:

1. Both num1 and num2 come from the array nums
2. When you calculate num1 OR num2 (bitwise OR) and num1 AND num2 (bitwise AND), then count the total number of set bits (1s) in both results, this sum must be at least k

For example, if num1 = 5 (binary: 101) and num2 = 3 (binary: 011):

• num1 OR num2 = 7 (binary: 111) has 3 set bits
• num1 AND num2 = 1 (binary: 001) has 1 set bit
• Total set bits = 3 + 1 = 4

The pairs (a, b) and (c, d) are considered different if either the first elements are different (a != c) or the second elements are different (b != d). This means (1, 2) and (2, 1) count as two distinct pairs.

You can also form a pair with the same number twice, like (num1, num1), as long as that number appears at least once in the array.

Your goal is to return the total count of all distinct excellent pairs.

The solution leverages a key mathematical property: the count of set bits in (A OR B) plus the count of set bits in (A AND B) equals the count of set bits in A plus the count of set bits in B. This allows the problem to be simplified by first removing duplicates from the array, counting the set bits for each unique number, and then checking all possible pairs to see if their combined bit counts meet or exceed k.

Intuition

The key insight comes from understanding a fundamental property of bitwise operations. When we look at num1 OR num2 and num1 AND num2, we're essentially examining how the bits of these two numbers interact.

Consider what happens at each bit position:

• If both numbers have a 1 at that position: OR gives 1, AND gives 1 (total: 2 bits)
• If only one number has a 1 at that position: OR gives 1, AND gives 0 (total: 1 bit)
• If both numbers have a 0 at that position: OR gives 0, AND gives 0 (total: 0 bits)

This reveals that the total count of set bits in (num1 OR num2) + (num1 AND num2) is exactly equal to the count of set bits in num1 plus the count of set bits in num2. Mathematically: bitcount(A OR B) + bitcount(A AND B) = bitcount(A) + bitcount(B).

This transformation is powerful because it converts our problem from checking complex bitwise operations for every pair to simply checking if the sum of bit counts of two numbers is at least k.

Since we only care about the bit counts and not the actual values for pairing, we can:

1. First remove duplicates from the array (using a set) since duplicate values would have the same bit count
2. Count how many numbers have each possible bit count value
3. For each unique number, check all possible bit count values and add up how many valid pairs can be formed

The solution avoids checking all n² pairs directly by grouping numbers by their bit counts, making it more efficient. For each number with bit count t, we look for all numbers whose bit count i satisfies t + i >= k, and add the count of such numbers to our answer.

Learn more about Binary Search patterns.

Solution Approach

The implementation follows these steps:

1. Remove duplicates: Convert the input array nums to a set s. This eliminates duplicate values since a number paired with itself will always produce the same result regardless of how many times it appears in the original array.

2. Count bit frequencies: Create a Counter dictionary cnt to track how many unique numbers have each specific bit count. We iterate through each unique number v in the set and increment cnt[v.bit_count()]. For example, if we have numbers 3 (binary: 11, 2 bits) and 5 (binary: 101, 2 bits), then cnt[2] = 2.

3. Count valid pairs: For each unique number v in the set:

   • Calculate its bit count t = v.bit_count()
   • Iterate through all entries (i, x) in the counter where i is a bit count value and x is how many numbers have that bit count
   • If t + i >= k, it means this number v can form excellent pairs with all x numbers that have bit count i
   • Add x to the answer

The algorithm works because:

• When we pair a number with bit count t with any number having bit count i, the condition for excellence becomes t + i >= k
• Each number in the set is considered as the first element of a pair
• For each such number, we count how many valid second elements exist based on bit count requirements
• This automatically handles both (a, b) and (b, a) as distinct pairs since each number gets a turn being the first element

Time Complexity: O(n × log(max_value)) where n is the number of unique elements and log(max_value) represents the maximum possible bit count.

Space Complexity: O(n) for storing the set and counter.

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 3, 1] and k = 3.

Step 1: Remove duplicates

• Convert nums to a set: s = {1, 2, 3}
• This removes the duplicate 1 since pairing with the same value always gives the same result

Step 2: Count bit frequencies

• For each unique number, count its set bits:
  • 1 (binary: 001) has 1 set bit
  • 2 (binary: 010) has 1 set bit
  • 3 (binary: 011) has 2 set bits
• Create counter: cnt = {1: 2, 2: 1}
  • This means 2 numbers have 1 set bit, and 1 number has 2 set bits

Step 3: Count valid pairs

• For v = 1 (bit count t = 1):

  • Check bit count 1: Since 1 + 1 = 2 < 3, skip
  • Check bit count 2: Since 1 + 2 = 3 >= 3, add cnt[2] = 1 to answer
  • Pairs formed: (1, 3)

• For v = 2 (bit count t = 1):

  • Check bit count 1: Since 1 + 1 = 2 < 3, skip
  • Check bit count 2: Since 1 + 2 = 3 >= 3, add cnt[2] = 1 to answer
  • Pairs formed: (2, 3)

• For v = 3 (bit count t = 2):

  • Check bit count 1: Since 2 + 1 = 3 >= 3, add cnt[1] = 2 to answer
  • Check bit count 2: Since 2 + 2 = 4 >= 3, add cnt[2] = 1 to answer
  • Pairs formed: (3, 1), (3, 2), (3, 3)

Total answer: 1 + 1 + 3 = 5

The excellent pairs are: (1, 3), (2, 3), (3, 1), (3, 2), (3, 3)

We can verify: For pair (1, 3):

• 1 OR 3 = 3 (binary: 011) has 2 set bits
• 1 AND 3 = 1 (binary: 001) has 1 set bit
• Total: 2 + 1 = 3 >= k ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m²) where n is the length of the input array nums and m is the maximum number of bits (at most 30 for typical integer constraints).

• Converting nums to a set takes O(n) time
• First loop iterates through the set (at most n elements) and counts bits for each element: O(n) time
• Second nested loop:
  • Outer loop iterates through the set: O(n) iterations
  • Inner loop iterates through the counter's keys (at most m different bit counts): O(m) iterations
  • Total for nested loops: O(n × m)
• Since m is bounded by the number of bits in an integer (typically 30), and in practice the counter will have at most m keys, the overall complexity is O(n × m) which simplifies to O(n) when m is treated as a constant

Space Complexity: O(n)

• The set s stores unique elements from nums: O(n) space in worst case
• The counter cnt stores at most m different bit counts (where m ≤ 30): O(m) space, which is O(1) when treating the bit width as constant
• Other variables (ans, t, i, x) use O(1) space
• Total space complexity: O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Counting Duplicate Numbers Multiple Times

Issue: A common mistake is not removing duplicates from the original array before processing. If you keep duplicates, you might incorrectly count pairs multiple times. For instance, if the array is [1, 1, 1] and you don't remove duplicates, you might count the pair (1, 1) three times instead of once.

Why it happens: The problem states that we can form pairs from elements in the array, which might lead to thinking we need to consider each occurrence separately. However, since bitwise operations on the same values always produce the same result, duplicate values don't create new distinct pairs.

Solution: Always convert the input array to a set first to eliminate duplicates:

unique_numbers = set(nums)  # Critical step - remove duplicates

Pitfall 2: Misunderstanding the Bit Count Property

Issue: Attempting to calculate (num1 OR num2).bit_count() + (num1 AND num2).bit_count() directly for each pair, leading to O(n²) complexity and potentially timeout on large inputs.

Why it happens: The problem description naturally suggests checking each pair individually, which seems like the straightforward approach.

Solution: Recognize and use the mathematical property that:

(A OR B).bit_count() + (A AND B).bit_count() == A.bit_count() + B.bit_count()

This allows you to precompute bit counts and group numbers by their bit count, reducing the problem to checking sums of bit counts.

Pitfall 3: Incorrect Pair Counting Logic

Issue: Only counting each valid combination once instead of considering both orderings. For example, counting (3, 5) but forgetting that (5, 3) is also a distinct pair according to the problem.

Why it happens: Traditional combination problems often treat (a, b) and (b, a) as the same, but this problem explicitly states they are different.

Solution: The correct approach iterates through each number as the first element and counts all valid second elements:

for number in unique_numbers:
    current_bit_count = number.bit_count()
    for other_bit_count, frequency in bit_count_frequency.items():
        if current_bit_count + other_bit_count >= k:
            excellent_pairs_count += frequency

This naturally handles both orderings since each number gets a turn being the first element in a pair.

Pitfall 4: Edge Case with Self-Pairs

Issue: Incorrectly handling or forgetting about pairs where both elements are the same number, like (5, 5).

Why it happens: It's easy to focus on pairs of different numbers and forget that a number can pair with itself.

Solution: The frequency-based counting approach automatically handles this correctly. When a number pairs with numbers having the same bit count (including itself), the frequency counter includes that number, so self-pairs are naturally counted.