Number of Excellent Pairs

Number of Excellent Pairs

What is this problem about?

The Number of Excellent Pairs problem asks you to count distinct ordered pairs (a, b) from an array (a and b can be the same element, but the pair must be formed from elements in the array) such that OR(a,b) and AND(a,b) together have at least k set bits. This hard Number of Excellent Pairs coding problem uses the property that popcount(OR(a,b)) + popcount(AND(a,b)) = popcount(a) + popcount(b).

Why is this asked in interviews?

Epifi asks this because it requires the non-obvious insight that popcount(a|b) + popcount(a&b) == popcount(a) + popcount(b) for all integers a and b. This reduces the problem to: count pairs where popcount(a) + popcount(b) >= k. Sort by popcount, deduplicate, and use binary search for counting. The array, hash table, binary search, and bit manipulation interview pattern is the core.

Algorithmic pattern used

Popcount transformation + binary search. For each unique element, compute its popcount. Deduplicate elements (use a set). Sort the unique popcounts. For each element with popcount p, count how many unique elements have popcount q such that p + q >= k. Binary search for the minimum valid q. Sum all counts (handle (a,b) and (b,a) as distinct ordered pairs).

Example explanation

nums=[1,2,3,1], k=3. Unique: {1,2,3}. Popcounts: 1→1, 2→1, 3→2. Sorted: [1,1,2]. For element with popcount 1: need partner with popcount ≥ 2. Count: 1 (element 3). Pairs: 2 (ordered: (1,3) and (2,3)). For element with popcount 2: need partner with popcount ≥ 1. Count: 3 (all). Pairs: 3 (ordered: (3,1),(3,2),(3,3)). Total = 2+2+3 = 7. (Adjust for double counting... careful with self-pairs.)

Common mistakes candidates make

• Not recognizing the popcount(OR) + popcount(AND) = popcount(a) + popcount(b) identity.
• Not deduplicating the array (a and b are values, not indices).
• Treating (a,b) and (b,a) as the same pair when they should be counted as distinct ordered pairs.
• Sorting elements instead of their popcount values.

Interview preparation tip

The identity popcount(a|b) + popcount(a&b) = popcount(a) + popcount(b) is a fundamental bit manipulation property. It follows from each bit being counted in OR+AND exactly as many times as in a+b individually. Memorize this identity — it simplifies several bit manipulation problems. After recognizing it, the problem reduces to a standard two-pointer or binary search count on sorted popcount values.