We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Excellent Pairs

Number: 2430

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed array of positive integers, nums, and a positive integer k, we define an excellent pair as a pair (num1, num2) where both num1 and num2 appear in nums and the sum of the number of set bits in (num1 OR num2) and (num1 AND num2) is at least k. Note that pairs (a, b) and (b, a) are considered distinct, and a pair with identical elements (num, num) is allowed if the element appears in the array.

Key Insights

  • Removing duplicates is important because only unique numbers matter for counting excellent pairs.
  • The number of set bits in (num1 OR num2) plus (num1 AND num2) simplifies to the sum of the bit counts of num1 and num2.
  • Bucket the numbers by their bit count (e.g. using an array where the index corresponds to the number of set bits) to enable efficient pairing.
  • Use a double loop over the possible bit counts (which is a constant range, e.g. up to 31 bits for numbers up to 10^9) to count all valid pairs based on the condition i + j >= k.

Space and Time Complexity

Time Complexity: O(n) + O(1)
  - O(n) to process the input array and compute bit counts
  - O(1) constant time for checking valid pairs since the loop is over a small constant range
Space Complexity: O(n) in the worst case (for storing unique numbers and their associated counts) or O(1) additional space if counting buckets are considered constant space.

Solution

The solution works as follows:

  1. Remove duplicate numbers from the array because repeated values do not contribute differently to the count.
  2. For each unique number, calculate its bit count using a built-in bit-counting operation, and then group these counts into buckets.
  3. For each possible pair of bit counts (i, j), if the condition (i + j >= k) is satisfied, then the number of pairs contributed is the product of their frequencies.
  4. Sum all such contributions to obtain the final count of excellent pairs.
  5. Since the number of possible bit counts is small (constant), iterating over the possible pairs is efficient.

Key data structures used include:

  • A set (or similar) for deduplication.
  • An array or dictionary to bucket numbers by bit counts.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Define the function that returns the number of excellent pairs
def countExcellentPairs(nums, k):
    # Remove duplicates from the nums list
    unique_nums = set(nums)
    
    # Create an array to count frequencies of set bits.
    # The maximum number of bits in numbers up to 10^9 is at most 31.
    bit_count_freq = [0] * 32
    
    # For each unique number, compute its bit count and update the bucket.
    for num in unique_nums:
        count = bin(num).count("1")
        bit_count_freq[count] += 1
        
    # Initialize the result counter
    result = 0
    
    # Iterate through all possible pairs of bit counts
    for i in range(32):
        for j in range(32):
            # If the sum of bit counts meets or exceeds k, count all pairs.
            if i + j >= k:
                result += bit_count_freq[i] * bit_count_freq[j]
                
    return result

# Example usage:
# print(countExcellentPairs([1, 2, 3, 1], 3)) # Expected output: 5
← Back to All Questions