Leetcode 1835. Find XOR Sum of All Pairs Bitwise AND

Problem

leetcode.com/contest/weekly-contest-237/problems/find-xor-sum-of-all-pairs-bitwise-and/

Account Login - LeetCode

Solving 1

Constraints를 보면,

• 1 <= arr1.length, arr2.length <= 10^5
• 0 <= arr1[i], arr2[j] <= 10^9

위와 같으므로 단순 nested loop로는 해결이 되지 않는다.

(a AND b) ^ (a AND c) = a AND (b^c) 임이 성립합을 이용하여 문제를 해결할 수 있다.

위의 식을 적용하면

(x0 AND y0) ^ (x0 AND y1) ^ ... ^ (x0 AND ym) = x0 AND (y1^y2^...^ym),
(x1 AND y0) ^ (x1 AND y1) ^ ... ^ (x1 AND ym) = x1 AND (y1^y2^...^ym),
...
(xn AND y0) ^ (xn AND y1) ^ ... ^ (xn AND ym) = xn AND (y1^y2^...^ym) 이므로,

x0 AND (y1^y2^...^ym) ^ x1 AND (y1^y2^...^ym) ^ ... ^ xn AND (y1^y2^...^ym) = (x1^x2^...^xn) AND (y1^y2^...^ym) 이다.

Solution1

class Solution {
public:
    int getXORSum(vector<int>& x, vector<int>& y) {
        int a = x[0];       
        for (int i = 1; i < x.size(); ++i) {
            a ^= x[i];
        }
        int b = y[0];       
        for (int i = 1; i < y.size(); ++i) {
            b ^= y[i];
        }
        return a & b;
    }
};

Solving 2

Bitwise XOR 연산은 각 자리의 1비트의 숫자가 홀수개이면 1, 짝수개이면 0이 된다.

벡터 x 에 있는 수 x1, x2, x3, ... xn과 벡터 y에 있는 수 y1, y2, y3, ... ym 의 모든 쌍에 대해서 bitwise AND 연산을 한 결과  x1 AND y1, x1 AND y2, .. y1 AND ym, x2 AND y1, x2 AND y2, ... x2 AND ym, ... , xn AND y1, xn AND y2, ..., xn AND ym 에 대해 한 비트씩 생각해보자. xp AND yq의 b번째 비트는 xp의 b번째 비트와  yq의 b번째 비트가 모두 1인 경우에만 1이 된다.

f_b(v) 를 벡터 v에 속한 모든 원소에 대해서 b번째 비트가 1인 갯수로 정의를 하고,
벡터 z = x 와 y의 모든 쌍에 대한 bitwise AND 연산 결과로 정의를 하면,
f_b(z) = f_b(x) * f_b(y) 임을 알 수 있다.

마지막으로 f_b(z)가 홀수인 경우, 혹은 f_b(x)와 f_b(y)가 모두 홀수인 경우, z에 속한 모든 원소에 bitwise XOR 연산을 적용한 결과 b번째 비트가 1임을 유도할 수 있다.

Solution2

class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int b1[31] = {0};
        int b2[31] = {0};
        for (int x: arr1) {
            for (int bi = 0; bi < 31; ++bi) {
                b1[bi] += (x & (1 << bi)) ? 1 : 0;
            }
        }
        for (int x: arr2) {
            for (int bi = 0; bi < 31; ++bi) {
                b2[bi] += (x & (1 << bi)) ? 1 : 0;
            }
        }
        int ans = 0;
        for (int bi = 0; bi < 31; ++bi) {
            if ((b1[bi] & 1) && (b2[bi] & 1)) {
                ans |= (1 << bi);
            }
        }
        return ans;
    }
};