zucyo05's blog

By zucyo05, history, 4 weeks ago, In English

The idea of the problem is bit-manipulation. (i.e. we can consider each bit independently and then aggregate our answer).

Now, consider we only have 0 's and 1 's in our array. For example, we have an array [1,0,1] as our arr1 and [0,1,1,1] as our arr2. We will have our result to be [0,1,1,1,0,0,0,0,0,1,1,1] and since there are even number of one's, we will consider the bit as 0 for our answer. We also notice the definition of bit-and is quite similar to multiplication. In fact, you can also consider indicator function for it by considering the underlying logic. We require both the element from arr1 and the element from arr2 to be one's to have contribution to our answer. And we also need to consider the basic principle of mathematics to count the number one's in our final array. Our result regarding the number of one's in our final array should be the multiplication of the number one's in arr1 and the number one's in arr2.

Now, we just need to enumerate the bit and you just need to exam if the bit occurs even or odd number of times in our final array.

C++ code: (using the transpiler cLay written by LayCurse but it should be quick to parse into c++ code )

class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int res = 0;
        int n = arr1.size(), m = arr2.size();
        rep(i, 0, 31){
            int cnt1 = 0;
            int cnt2 = 0;
            rep(j, 0, n){
                auto x = arr1[j];
                if((x >> i) & 1){
                    ++cnt1;
                    cnt1 %= 2;
                }
            }
            rep(j, 0, m){
                auto x = arr2[j];
                if((x >> i) & 1){
                    ++cnt2;
                    cnt2 %= 2;
                }
            }
            if((cnt1 * cnt2)%2 == 1){
                res |= (1<<i);
            }
        }
        return res;
    }
};

Link: Your text to link here...

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zucyo05 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This reminds me of 1323D - Present

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

What I can see here is the editorial of the problem. Why don't you post this in Leetcode's problem discussion instead of here?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And THIS is a form of protest against leetcode censorship