number-of-excellent-pairs

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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

<ul>
	<li>Both 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 OR operation and <code>AND</code> is the bitwise AND operation.</li>
</ul>

Return the number of distinct excellent pairs.

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.

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

&nbsp;
Example 1:

<pre>
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.</pre>

Example 2:

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= 60</code></li>
</ul>

countExcellentPairs

Number of Excellent Pairs

Two Sum

two-sum

两数之和

Bit Manipulation

Array

Hash Table

Binary Search

给你一个下标从 0 开始的正整数数组 <code>nums</code> 和一个正整数 <code>k</code> 。

如果满足下述条件，则数对 <code>(num1, num2)</code> 是 优质数对 ：

<ul>
	<li><code>num1</code> 和 <code>num2</code> 都 在数组 <code>nums</code> 中存在。</li>
	<li><code>num1 OR num2</code> 和 <code>num1 AND num2</code> 的二进制表示中值为 1 的位数之和大于等于 <code>k</code> ，其中 <code>OR</code> 是按位 或 操作，而 <code>AND</code> 是按位 与 操作。</li>
</ul>

返回 不同 优质数对的数目。

如果&nbsp;<code>a != c</code> 或者 <code>b != d</code> ，则认为 <code>(a, b)</code> 和 <code>(c, d)</code> 是不同的两个数对。例如，<code>(1, 2)</code> 和 <code>(2, 1)</code> 不同。

注意：如果 <code>num1</code> 在数组中至少出现 一次 ，则满足 <code>num1 == num2</code> 的数对 <code>(num1, num2)</code> 也可以是优质数对。

&nbsp;

示例 1：

<pre>
输入：nums = [1,2,3,1], k = 3
输出：5
解释：有如下几个优质数对：
- (3, 3)：(3 AND 3) 和 (3 OR 3) 的二进制表示都等于 (11) 。值为 1 的位数和等于 2 + 2 = 4 ，大于等于 k = 3 。
- (2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
- (1, 3) 和 (3, 1)： (1 AND 3) 的二进制表示等于 (01) ，(1 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
所以优质数对的数目是 5 。</pre>

示例 2：

<pre>
输入：nums = [5,1,1], k = 10
输出：0
解释：该数组中不存在优质数对。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= 60</code></li>
</ul>