LeetCode 2354 - Number of Excellent Pairs

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Binary Search, Bit Manipulation

Solution

Problem Understanding

The problem provides a 0-indexed array of positive integers nums and a positive integer k. The task is to count all distinct pairs (num1, num2) such that both numbers exist in nums and the sum of the number of set bits in num1 OR num2 and num1 AND num2 is at least k. A pair (num1, num2) is considered distinct from (num2, num1) even if the numbers are the same. Pairs where num1 == num2 are allowed.

Formally, for a pair (a, b) to be excellent, it must satisfy:

count_bits(a | b) + count_bits(a & b) >= k

where count_bits(x) is the number of 1s in the binary representation of x.

The constraints tell us that nums can be very large (up to 100,000 elements) and the values in nums can be large (up to 10^9). This means that a naive double loop over all pairs would be too slow. The problem also emphasizes that the pair counting must be careful to avoid duplicates when num1 != num2 and must allow num1 == num2 correctly.

Important edge cases include arrays where all elements are identical, arrays where no pair satisfies k, and arrays containing very large integers where bit counts are close to 30, as nums[i] <= 10^9.

Approaches

The brute-force approach would iterate over all pairs (i, j) where i and j index the array, compute (nums[i] | nums[j]) and (nums[i] & nums[j]), count the set bits, and check if the sum is greater than or equal to k. This is correct but has a time complexity of O(n^2), which is infeasible for n up to 10^5.

The key insight for an optimal approach is to observe the following:

count_bits(a | b) + count_bits(a & b) = count_bits(a) + count_bits(b)

This is a crucial bit-manipulation property. It allows us to replace the bitwise operations on pairs with a much simpler sum of bit counts for each number. Therefore, instead of checking (a | b) and (a & b), we only need the number of set bits for each unique number in nums.

Next, we can reduce duplicate calculations by storing unique numbers in nums. We convert each number to its bit_count and sort these counts. Then, for each bit count c1, we can use binary search to count the number of c2 such that c1 + c2 >= k.

This leads to a much faster algorithm.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Check all pairs directly. Too slow for n=1e5
Optimal	O(n log n)	O(n)	Use unique values, count bits, sort, and binary search

Algorithm Walkthrough

Remove duplicates from nums to reduce unnecessary computations. This ensures we count distinct pairs correctly.
Compute the number of set bits for each unique number in nums using a function like bin(num).count('1') in Python.
Sort the list of bit counts. Sorting allows efficient binary search to find complements.
Initialize a counter total_pairs = 0.
For each bit count c1 in the sorted list, compute target = k - c1. This is the minimum bit count c2 required to form an excellent pair.
Use binary search to find the index of the first c2 >= target in the sorted list.
The number of valid c2 values for this c1 is len(bit_counts) - index. Add this count to total_pairs.
After iterating all c1, return total_pairs. Each pair is automatically counted distinctly because we count combinations from sorted bit counts.

Why it works: The property count_bits(a | b) + count_bits(a & b) = count_bits(a) + count_bits(b) reduces the problem to a sum check of bit counts. By using sorted bit counts and binary search, we efficiently count all pairs satisfying the sum condition without explicitly iterating all n^2 combinations. Deduplication ensures correctness for unique numbers.

Python Solution

from typing import List
import bisect

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        unique_nums = list(set(nums))
        bit_counts = [bin(num).count('1') for num in unique_nums]
        bit_counts.sort()
        
        total_pairs = 0
        n = len(bit_counts)
        
        for c1 in bit_counts:
            target = k - c1
            idx = bisect.bisect_left(bit_counts, target)
            total_pairs += n - idx
        
        return total_pairs

In this implementation, we first remove duplicates using set(nums). Then we compute the bit counts and sort them. For each c1, we determine the smallest c2 that satisfies the sum using bisect_left. The result accumulates all valid pairs efficiently.

Go Solution

import (
    "sort"
    "math/bits"
)

func countExcellentPairs(nums []int, k int) int64 {
    uniqueMap := make(map[int]struct{})
    for _, num := range nums {
        uniqueMap[num] = struct{}{}
    }
    
    bitCounts := make([]int, 0, len(uniqueMap))
    for num := range uniqueMap {
        bitCounts = append(bitCounts, bits.OnesCount(uint(num)))
    }
    
    sort.Ints(bitCounts)
    var totalPairs int64 = 0
    n := len(bitCounts)
    
    for _, c1 := range bitCounts {
        target := k - c1
        idx := sort.Search(n, func(i int) bool { return bitCounts[i] >= target })
        totalPairs += int64(n - idx)
    }
    
    return totalPairs
}

In Go, we use a map to remove duplicates and bits.OnesCount to count set bits. sort.Search implements binary search to efficiently find the first index meeting the target sum condition.

Worked Examples

Example 1: nums = [1,2,3,1], k = 3

Step	Unique nums	Bit counts	Total pairs calculation
1	[1,2,3]	[1,1,2]	sorted → [1,1,2]
2	c1 = 1	target = 2	idx = 2 → pairs = 1
3	c1 = 1	target = 2	idx = 2 → pairs = 1 (total 2)
4	c1 = 2	target = 1	idx = 0 → pairs = 3 (total 5)

Result: 5

Example 2: nums = [5,1,1], k = 10

Step	Unique nums	Bit counts	Total pairs calculation
1	[1,5]	[1,2]	sorted → [1,2]
2	c1 = 1	target = 9	idx = 2 → 0 pairs
3	c1 = 2	target = 8	idx = 2 → 0 pairs

Result: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Removing duplicates is O(n), counting bits is O(n * log(max_num)) ~ O(n * 30), sorting is O(n log n), binary search for each element is O(n log n) overall
Space	O(n)	Store unique numbers and their bit counts

The algorithm is efficient for n up to 10^5, and bit counting is cheap since each integer is at most 30 bits.

Test Cases

# provided examples
assert Solution().countExcellentPairs([1,2,3,1], 3) == 5  # multiple excellent pairs
assert Solution().countExcellentPairs([5,1,1], 10) == 0   # no excellent pairs

# boundary tests
assert Solution().countExcellentPairs([1], 1) == 1        # single element, pair with itself
assert Solution().countExcellentPairs([1], 2) == 0        # sum of bits less than k
assert Solution().countExcellentPairs([1,3,7,15], 5) == 10 # multiple combinations

# all identical numbers
assert Solution().countExcellentPairs([4,4,4,4], 2) == 16  # each can pair with each

# large numbers
assert Solution().countExcellentPairs([2**30, 2**30-1], 30) == 4  # test high bit counts

Test	Why
[1,2,3,1], k=3	Validates multiple excellent pairs