Number of Excellent Pairs - Practice Coding Problems

Number of Excellent Pairs - Problem

You are given a 0-indexed positive integer array nums and a positive integer k.

A pair of numbers (num1, num2) is called excellent if the following conditions are satisfied:

Both the numbers num1 and num2 exist in the array nums.
The sum of the number of set bits in num1 OR num2 and num1 AND num2 is greater than or equal to k, where OR is the bitwise OR operation and AND is the bitwise AND operation.

Return the number of distinct excellent pairs.

Two pairs (a, b) and (c, d) are considered distinct if either a != c or b != d. For example, (1, 2) and (2, 1) are distinct.

Note that a pair (num1, num2) such that num1 == num2 can also be excellent if you have at least one occurrence of num1 in the array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,5], k = 5

› Output: 4

💡 Note: Pairs (1,5), (2,5), (3,5), (5,5) have bit sums >= 5. For (3,5): bits(3|5) + bits(3&5) = bits(7) + bits(1) = 3 + 1 = 4 < 5, but (5,5): bits(5|5) + bits(5&5) = bits(5) + bits(5) = 3 + 3 = 6 >= 5.

Example 2 — All Pairs Valid

$ Input: nums = [5,1,3], k = 3

› Output: 5

💡 Note: All pairs except (1,1) are excellent. 1 has 1 bit, 3 has 2 bits, 5 has 2 bits. Valid: (1,3), (1,5), (3,1), (3,5), (5,5).

Example 3 — No Valid Pairs

$ Input: nums = [1,2], k = 5

› Output: 0

💡 Note: Maximum bit sum is 1+1=2 for (1,2), which is less than k=5. No excellent pairs exist.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 60

Visualization

Tap to expand

Understanding the Visualization

Input

Array of numbers and threshold k

Process

Find pairs where bits(a|b) + bits(a&b) >= k

Output

Count of excellent pairs

Key Takeaway

🎯 Key Insight: Use the mathematical property bits(a|b) + bits(a&b) = bits(a) + bits(b) to avoid expensive bitwise operations

Asked in

G Google 12 M Meta 8 M Microsoft 6

The key insight is using the mathematical property that bits(a|b) + bits(a&b) = bits(a) + bits(b). Instead of computing OR and AND for each pair, group numbers by bit count and multiply combinations. Best approach is bit count grouping with Time: O(n + B²), Space: O(B).

Common Approaches

Approach	Time	Space	Notes
✓ Bit Count Grouping	O(n + B²)	O(B)	Use the mathematical property that bits(a\|b) + bits(a&b) = bits(a) + bits(b)
Brute Force	O(n² × log(max(nums)))	O(n)	Check every pair of numbers and count set bits in their OR and AND operations

Bit Count Grouping — Algorithm Steps

Remove duplicates and count bit counts
Group numbers by their bit count
For each pair of bit counts, check if sum >= k
Count all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Bits

Group numbers by their bit count

Mathematical Property

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

Count Combinations

Multiply counts for valid bit sum pairs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countBits(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

long long solution(int* nums, int numsSize, int k) {
    int unique[1000];
    int uniqueSize = 0;
    
    // Remove duplicates
    for (int i = 0; i < numsSize; i++) {
        int found = 0;
        for (int j = 0; j < uniqueSize; j++) {
            if (unique[j] == nums[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            unique[uniqueSize++] = nums[i];
        }
    }
    
    // Count set bits for each unique number
    int bitCounts[33] = {0}; // max 32 bits
    for (int i = 0; i < uniqueSize; i++) {
        int bits = countBits(unique[i]);
        bitCounts[bits]++;
    }
    
    long long count = 0;
    // For each pair of bit counts
    for (int bits1 = 0; bits1 <= 32; bits1++) {
        if (bitCounts[bits1] == 0) continue;
        for (int bits2 = 0; bits2 <= 32; bits2++) {
            if (bitCounts[bits2] == 0) continue;
            if (bits1 + bits2 >= k) {
                count += (long long) bitCounts[bits1] * bitCounts[bits2];
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%lld\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + B²)

O(n) to count bits for each number, O(B²) to check pairs where B <= 32 is max bits

✓ Linear Growth

Space Complexity

O(B)

Array to store count of numbers for each bit count, B <= 32

✓ Linear Space

18.5K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Count Grouping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler