<p>You are given a <strong>0-indexed</strong> positive integer array <code>nums</code> and a positive integer <code>k</code>.</p>

<p>A pair of numbers <code>(num1, num2)</code> is called <strong>excellent</strong> if the following conditions are satisfied:</p>

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

<p>Return <em>the number of <strong>distinct</strong> excellent pairs</em>.</p>

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

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,1], k = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> 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.</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= k &lt;= 60</code></li>
</ul>

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:

        '''
        case1: 00, 11 => AND + OR = 0 + 2 = 2
        case2: 01, 10 => AND + OR = 0 + 2 = 2
        case3: 00, 00 => 0 + 0 = 0
        case4: 11, 11 => 2 + 2 = 4
        case5: 11, 10 => 1 + 2 = 3 

        so basically we finding the totl number of set bits in num1 and num2
        we can consider to remove duplicates in the given list
        we only need to find number of pairs
        only store the number of bits instead of the real number bin(n).count('1')
        and we finding two sum problem 
        do a sorting while pushing the bits 
        then use two pointers to validate the sum
        '''

        nums_pairs = 0

        nums_bits = []
        for num in set(nums):
            nums_bits.append(bin(num).count('1'))
        nums_bits.sort()

        left = 0
        right = len(nums_bits) - 1
        while left <= right:
            if nums_bits[left] + nums_bits[right] >= k:
                nums_pairs += (right - left) * 2 + 1
                right -= 1
            else:
                left += 1
        
        return nums_pairs
584