Number of Excellent Pairs

Hard
1330.

Number of Excellent Pairs

Number of Excellent Pairs is a hard coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.

You are given an array nums of positive integers and a positive integer k. A pair of numbers (num1, num2) is excellent when:

  • both num1 and num2 occur in nums, and
  • the number of set bits in num1 OR num2 plus the number of set bits in num1 AND num2 is at least k.

Pairs are ordered and compared by value: (a, b) and (b, a) are different pairs when a != b, while repeated occurrences of the same values give the same pair. num1 and num2 may be the same value, as long as it occurs at least once.

Return the number of distinct excellent pairs.

CodeKairo bound: the original allows 10^5 elements, whose answer needs 64 bits; here nums.length <= 4 * 10^4, so the answer fits a 32-bit integer.

Example 1

Input
nums = [5,1,6,5], k = 4
Output
4
Explanation
5 and 6 each have 2 set bits. The pairs (5,5), (5,6), (6,5) and (6,6) reach 4; any pair with 1 reaches at most 3.

Example 2

Input
nums = [7,8], k = 5
Output
1
Explanation
Only (7,7): 3 + 3 = 6.

Example 3

Input
nums = [3], k = 10
Output
0

Constraints

  • 1 <= nums.length <= 4 * 10^4
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 60
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countExcellentPairs = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Excellent Pairs — Solution in Python, Java & C++

Number of Excellent Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Number of Excellent Pairs is a hard coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.

Problem statement

You are given an array nums of positive integers and a positive integer k. A pair of numbers (num1, num2) is excellent when:

  • both num1 and num2 occur in nums, and
  • the number of set bits in num1 OR num2 plus the number of set bits in num1 AND num2 is at least k.

Pairs are ordered and compared by value: (a, b) and (b, a) are different pairs when a != b, while repeated occurrences of the same values give the same pair. num1 and num2 may be the same value, as long as it occurs at least once.

Return the number of distinct excellent pairs.

CodeKairo bound: the original allows 10^5 elements, whose answer needs 64 bits; here nums.length <= 4 * 10^4, so the answer fits a 32-bit integer.

Example 1

Input: nums = [5,1,6,5], k = 4
Output: 4
Explanation: 5 and 6 each have 2 set bits. The pairs (5,5), (5,6), (6,5) and (6,6) reach 4; any pair with 1 reaches at most 3.

Example 2

Input: nums = [7,8], k = 5
Output: 1
Explanation: Only (7,7): 3 + 3 = 6.

Example 3

Input: nums = [3], k = 10
Output: 0

Constraints

  • 1 <= nums.length <= 4 * 10^4
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 60

Hints for Number of Excellent Pairs

  1. Hint 1

    Count the bits of a OR b and of a AND b bit by bit: what is their sum in terms of a and b alone?

  2. Hint 2

    A bit set in both counts twice, a bit set in one counts once — so the sum is popcount(a) + popcount(b).

  3. Hint 3

    Deduplicate nums, bucket the distinct values by popcount (at most 30 buckets), and add cnt[i] * cnt[j] for every i + j >= k.

How to solve Number of Excellent Pairs

popcount(a OR b) + popcount(a AND b) = popcount(a) + popcount(b), so a pair is excellent based only on the two popcounts, and the counting collapses to at most 30 × 30 bucket pairs.

Approach

  1. Remove duplicate values from nums.
  2. Count the distinct values by popcount: cnt[p] for p from 0 to 30.
  3. Sum cnt[i] * cnt[j] over all i, j with i + j >= k and return it.

Why it works

Look at one bit. If it is set in both numbers it contributes 1 to the OR and 1 to the AND; if set in exactly one it contributes 1 to the OR only; otherwise nothing. That is exactly its contribution to popcount(a) + popcount(b). Ordered pairs of distinct values (a, b) with popcounts (i, j) number cnt[i] * cnt[j], including a = b when i = j.

Complexity

  • Time — O(n + 30²)
  • Space — O(n)

Pitfalls

  • Deduplicate first — pairs are counted by value, not by index.
  • Pairs are ordered, so (a, b) and (b, a) are both counted, and (a, a) counts once.
  • In languages with 32-bit ints, accumulate the sum in a 64-bit variable even though the tightened answer fits.

Reference solution

Python

from typing import List

def countExcellentPairs(nums: List[int], k: int) -> int:
    cnt = [0] * 32
    for v in set(nums):
        cnt[bin(v).count("1")] += 1
    total = 0
    for i in range(32):
        for j in range(32):
            if i + j >= k:
                total += cnt[i] * cnt[j]
    return total

Java

public static int countExcellentPairs(int[] nums, int k) {
    long[] cnt = new long[32];
    Set<Integer> seen = new HashSet<>();
    for (int v : nums) if (seen.add(v)) cnt[Integer.bitCount(v)]++;
    long total = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < 32; j++) {
            if (i + j >= k) total += cnt[i] * cnt[j];
        }
    }
    return (int) total;
}

C++

int countExcellentPairs(vector<int>& nums, int k) {
    vector<long long> cnt(32, 0);
    unordered_set<int> seen(nums.begin(), nums.end());
    for (int v : seen) cnt[__builtin_popcount(v)]++;
    long long total = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < 32; j++) {
            if (i + j >= k) total += cnt[i] * cnt[j];
        }
    }
    return (int) total;
}

JavaScript

var countExcellentPairs = function(nums, k) {
    var cnt = new Array(32).fill(0);
    var seen = new Set(nums);
    seen.forEach(function(v) {
        var c = 0;
        while (v) { c += v & 1; v >>>= 1; }
        cnt[c]++;
    });
    var total = 0;
    for (var i = 0; i < 32; i++) {
        for (var j = 0; j < 32; j++) {
            if (i + j >= k) total += cnt[i] * cnt[j];
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets