Leetcode-6127: number of high-quality pairs

subject

Topic linking
I'll give you a subscript from 0 Starting array of positive integers nums And a positive integer k .

If the following conditions are met , Then number pair (num1, num2) yes High quality pairs ：

• num1 and num2 all In the array nums in .
• num1 OR num2 and num1 AND num2 The median value of the binary representation of is 1 The sum of digits of is greater than or equal to k , among OR It's bit by bit or operation , and AND It's bit by bit And operation .

return Different The number of high-quality pairs .

If a != c perhaps b != d , Think (a, b) and (c, d) Are two different number pairs . for example ,(1, 2) and (2, 1) Different .

Be careful ： If num1 At least... Appears in the array once , Then meet num1 == num2 The number of (num1, num2) It can also be a high-quality number pair .

Example 1：

 Input ：nums = [1,2,3,1], k = 3
 Output ：5
 explain ： There are several high-quality pairs as follows ：
- (3, 3)：(3 AND 3)  and  (3 OR 3)  The binary representation of is equal to  (11) . The value is  1  The sum of digits of is equal to  2 + 2 = 4 , Greater than or equal to  k = 3 .
- (2, 3)  and  (3, 2)： (2 AND 3)  The binary representation of is equal to  (10) ,(2 OR 3)  The binary representation of is equal to  (11) . The value is  1  The sum of digits of is equal to  1 + 2 = 3 .
- (1, 3)  and  (3, 1)： (1 AND 3)  The binary representation of is equal to  (01) ,(1 OR 3)  The binary representation of is equal to  (11) . The value is  1  The sum of digits of is equal to  1 + 2 = 3 .
 So the number of high-quality pairs is  5 .

Example 2：

 Input ：nums = [5,1,1], k = 10
 Output ：0
 explain ： There are no good number pairs in this array .

Problem solving

Method 1 ： Equivalent conversion

about x|y and x&y Medium 1, On the same bit , If there are both 1, So this one 1 Will be counted twice ; If one is for 1 For another 0, So this one 1 Will be counted once .
Therefore, it can be replaced equivalently , And 、 Or the result Binary bit of 1 The number of and , That is, two numbers are binary digits 1 The number of and .

Reference link

class Solution {
    
public:
    int getBits(int num){
    
        int res=0;
        while(num){
    
            res+=num&1;
            num>>=1;
        }
        return res;
    }

    long long countExcellentPairs(vector<int>& nums, int k) {
    

        // duplicate removal 
        sort(nums.begin(),nums.end());
        nums.resize(unique(nums.begin(),nums.end())-nums.begin());
        // nums.erase(unique(nums.begin(),nums.end()),nums.end()); // Either of these can be 

        int n=nums.size();
        vector<int> cnt(64,0);//bits Number  ----> Number 
        for(int i=0;i<n;i++){
    
            int bits=getBits(nums[i]);// Seeking position 1 The number of 
            cnt[bits]++;
        }
        long long res=0;
        for(int i=1;i<=60;i++){
    
            for(int j=1;j<=60;j++){
    
                if(i+j>=k){
    
                    res+=1ll*cnt[i]*cnt[j];
                }
            }
        }
        return res;
    }
};