Find the Prefix Common Array of Two Arrays

Leetcode Problem:

• Find the Prefix Common Array of Two Arrays

Summary

• Find the prefix common array of two integer permutations

Approach

• The approach is to use bitwise operations to count the common elements in both permutations
• The idea is to treat each permutation as a subset of numbers from 1 to n, where n is the length of the permutations
• We use a binary number to represent each subset, where each bit corresponds to a number from 1 to n
• We then use bitwise operations to count the common elements in both subsets.

Complexity

• O(n log n) due to the bitCount function, where n is the length of the permutations

Explanation

• The solution works by iterating over each element in both permutations and updating the subset numbers for each permutation
• For each element, we use bitwise operations to count the common elements in both subsets
• The bitCount function is used to count the number of bits set in a binary number, which represents the count of common elements
• The result is a vector of integers representing the prefix common array.

Solution Code:

class Solution {
public:
    int bitCount(unsigned long long num){
        int cnt = 0;
        while(num){
            cnt++;
            num &= num-1;
        }
        return cnt;
    }
    vector findThePrefixCommonArray(vector& A, vector& B) {
        unsigned long long subsetA = 0;
        unsigned long long subsetB = 0;
        vector ans;
        for(int i = 0 ; i < A.size(); i++){
            subsetA |= 1ULL << A[i];
            subsetB |= 1ULL << B[i];
            ans.push_back(bitCount(subsetA & subsetB));
        }
        return  ans;
    }
};