Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2354.html
2354. Number of Excellent Pairs
- Difficulty: Hard.
- Related Topics: Array, Hash Table, Binary Search, Bit Manipulation.
- Similar Questions: Two Sum.
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
andnum2
exist in the arraynums
. -
The sum of the number of set bits in
num1 OR num2
andnum1 AND num2
is greater than or equal tok
, whereOR
is the bitwise OR operation andAND
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
Solution
-
class Solution { public long countExcellentPairs(int[] nums, int k) { long[] cnt = new long[30]; long res = 0L; Set<Integer> set = new HashSet<>(); for (int a : nums) { 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; } } ############ class Solution { public long countExcellentPairs(int[] nums, int k) { Set<Integer> s = new HashSet<>(); for (int v : nums) { s.add(v); } long ans = 0; int[] cnt = new int[32]; for (int v : s) { int t = Integer.bitCount(v); ++cnt[t]; } for (int v : s) { int t = Integer.bitCount(v); for (int i = 0; i < 32; ++i) { if (t + i >= k) { ans += cnt[i]; } } } return ans; } }
-
class Solution: def countExcellentPairs(self, nums: List[int], k: int) -> int: s = set(nums) ans = 0 cnt = Counter() for v in s: cnt[v.bit_count()] += 1 for v in s: t = v.bit_count() for i, x in cnt.items(): if t + i >= k: ans += x return ans ############ # 2354. Number of Excellent Pairs # https://leetcode.com/problems/number-of-excellent-pairs/ class Solution: def countExcellentPairs(self, nums: List[int], k: int) -> int: nums = set(nums) MAX = 32 bits = [0] * MAX for x in nums: bits[x.bit_count()] += 1 res = 0 for i in range(1, MAX): for j in range(1, MAX): if i + j >= k: res += bits[i] * bits[j] return res
-
class Solution { public: long long countExcellentPairs(vector<int>& nums, int k) { unordered_set<int> s(nums.begin(), nums.end()); vector<int> cnt(32); for (int v : s) ++cnt[__builtin_popcount(v)]; long long ans = 0; for (int v : s) { int t = __builtin_popcount(v); for (int i = 0; i < 32; ++i) { if (t + i >= k) { ans += cnt[i]; } } } return ans; } };
-
func countExcellentPairs(nums []int, k int) int64 { s := map[int]bool{} for _, v := range nums { s[v] = true } cnt := make([]int, 32) for v := range s { t := bits.OnesCount(uint(v)) cnt[t]++ } ans := 0 for v := range s { t := bits.OnesCount(uint(v)) for i, x := range cnt { if t+i >= k { ans += x } } } return int64(ans) }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).