<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>

'''
算法原理
去重和统计 1 的个数:

首先将输入数组 nums 转换为集合，以去重并删除重复的元素，这样可以减少后续处理的计算量。
然后对每个数字，使用 bin(x).count('1') 计算其二进制表示中 1 的个数，并存储在 arr 列表中。
统计 1 的个数出现的频次:

使用 Counter 对 arr 中每个 1 的个数进行频次统计，存储在 cnt 字典中。键是 1 的个数，值是对应个数的频次。
寻找优秀对:

遍历 cnt 字典中所有可能的 (i, j) 组合，其中 i 和 j 是不同的 1 的个数。
对于每一个 (i, j) 组合，检查它们的和 i + j 是否大于等于 k。如果满足条件，则这个组合可以形成优秀对。
累加满足条件的优秀对的数量到 res 中。
返回结果:

返回累加后的结果 res，即优秀对的总数量。
复杂度分析
时间复杂度：O(n + m^2)，其中 n 是去重后的 nums 长度，m 是不同 1 的个数的数量。
计算每个数字的二进制 1 的个数并进行统计的时间复杂度为 O(n)。
由于需要遍历所有可能的 (i, j) 组合，双重循环的时间复杂度为 O(m^2)。
空间复杂度：O(m)，其中 m 是不同 1 的个数的数量。
需要额外的空间来存储计数器 cnt 和 arr 列表。
总结
这个算法通过将输入数组去重、计算每个数字的二进制 1 的个数，并通过双重循环遍历可能的组合来计算符合条件的优秀对。
算法的设计利用了计数器 Counter 和频次统计，优化了处理和计算流程，确保了复杂度在可以接受的范围内。
'''

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        # 将输入数组 nums 转换为集合，以去重并删除重复的元素
        nums = list(set(nums))
        
        # 创建一个列表 arr，其中存储了每个数字的二进制表示中 '1' 的个数
        arr = [bin(x).count('1') for x in nums]
        
        # 获取数组 arr 的长度
        n = len(arr)
        
        # 统计每个 '1' 的个数出现的频次，存储在字典 cnt 中
        cnt = Counter(arr)
        
        res = 0  # 初始化结果变量，用于存储符合条件的优秀对的数量
        
        # 遍历 cnt 中的所有可能的 (i, j) 组合，i 和 j 是不同的 '1' 的个数
        for i, cnt_i in cnt.items():
            for j, cnt_j in cnt.items():
                # 如果 i + j 的和大于等于 k，说明这个组合可以形成优秀对
                if i + j >= k:
                    # 累加符合条件的优秀对的数量
                    res += cnt_i * cnt_j
        
        return res  # 返回优秀对的总数量

531