Number of Excellent Pairs LeetCode Solution

Problem – Number of Excellent Pairs LeetCode Solution

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.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: 5
Explanation: The excellent pairs are the following:
- (3, 3). (3 AND 3) and (3 OR 3) are both equal to (11) in binary. The total number of set bits is 2 + 2 = 4, which is greater than or equal to k = 3.
- (2, 3) and (3, 2). (2 AND 3) is equal to (10) in binary, and (2 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3.
- (1, 3) and (3, 1). (1 AND 3) is equal to (01) in binary, and (1 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3.
So the number of excellent pairs is 5.

Example 2:

Input: nums = [5,1,1], k = 10
Output: 0
Explanation: There are no excellent pairs for this array.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 60

Number of Excellent Pairs LeetCode Solution in Java

    public long countExcellentPairs(int[] A, int k) {
        long cnt[] = new long[30], res = 0;
        Set<Integer> set = new HashSet<>();
        for (int a : A)
            set.add(a);
        for (int a : set)
            cnt[Integer.bitCount(a)]++;
        for (int i = 1; i < 30; ++i)
            for (int j = 1; j < 30; ++j)
                if (i + j >= k)
                    res += cnt[i] * cnt[j];
        return res;
    }

Number of Excellent Pairs LeetCode Solution in C++

    long long countExcellentPairs(vector<int>& A, int k) {
        long long cnt[30] = {}, res = 0;
        for (int a : unordered_set<int>(begin(A), end(A)))
            ++cnt[__builtin_popcount(a)];
        for (int i = 1; i < 30; ++i)
            for (int j = 1; j < 30; ++j)
                if (i + j >= k)
                    res += cnt[i] * cnt[j];
        return res;
    }

Number of Excellent Pairs LeetCode Solution in Python

class Solution:
    def countExcellentPairs(self, A: List[int], k: int) -> int:
        # Count number of bits in (n) in binary
        def numOfBits(n):
            ans = 0
            while n:
                ans += (n & 1)
                n >>= 1
            return ans
        
        # Sort the number of bits of each distinct number from A
        B = sorted([numOfBits(a) for a in set(A)])
        
        # Right pointer start at n - 1.
        n, j, ans = len(B), len(B) - 1, 0

        for i in range(n):
            # If the starting i, j don't meet the condition, continue for the next i.
            if B[i] + B[j] < k: 
                continue
            
            # Move until j = 0 or B[i] + B[j] < k
            while j >= 1 and B[i] + B[j - 1] >= k:
                j -= 1
                
            # All the number to the right of the pointer j (inclusive) make no less
            # sum of bits with B[i]
            ans += n - j
        
        return ans
Number of Excellent Pairs LeetCode Solution Review:

In our experience, we suggest you solve this Number of Excellent Pairs LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Number of Excellent Pairs LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Number of Excellent Pairs LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.