1835. Find XOR Sum of All Pairs Bitwise AND

 

https://leetcode.com/problems/find-xor-sum-of-all-pairs-bitwise-and/

Find XOR Sum of All Pairs Bitwise AND - LeetCode

---

문제

주어진 두 배열의 모든 원소 쌍을 각각 \(AND\) 연산한 결과를 이용하여 누적 \(XOR\) 값을 구하자

---

풀이

우선 배열의 모든 원소 쌍의 \(AND\) 값을 구하는 것은\(O(N^2)\) 시간이 걸리므로 \(N (\leq 10^5)\)의 크기를 봤을 때 그리 좋은 생각이 아닌 것 같다. 그렇다면 모든 원소 쌍을 보는 것은 불가능하고 각 배열을 한 번씩 훑어보는 정도는 할만한 것 같다. 배열을 한 번씩만 훑어보고 모든 원소 쌍의 \(AND\) 연산을 구할 수 있을까?

 

결론부터 말하자면 모든 원소쌍의 \(AND\) 연산을 구할 필요는 없다. \(XOR\)이 어떤 식으로 계산이 이루어지는지를 이해했다면 말이다. 

 

 

\(XOR\)은 결과적으로 봤을 때 모든 숫자를 훑어보고 켜져 있는 bit의 개수가 홀수라면 1, 짝수라면 0이 된다. 그렇다면 굳이 모든 원소 쌍의 \(AND\) 연산을 구할게 아니라, 모든 원소쌍을 \(AND\) 연산하여 만든 수열에 있는 숫자들을 훑어보고 각 bit가 몇 개씩 켜져 있는지만 알 수 있다면 문제를 해결할 수 있다. 그래서 이 값을 어떻게 알 수 있을까?

 

두 수의 \(AND\) 연산은, 각 자리의 bit가 두 숫자 모두에서 켜져 있는 경우에만 1이 결과로 나온다. 그렇다면 한쪽 배열에서 모든 숫자의 각 bit가 몇 개씩 켜져 있는지를 배열로 구해놓고, 반대쪽 배열에서는 각 bit가 켜져 있는 경우 그 값을 누적해서 더해나간다면 모든 원소 쌍을 \(AND\) 연산하여 만든 수열에 있는 수들의 각 bit가 몇개씩 켜져 있는지 알 수 있다. 즉 아래와 같은 순서로 문제를 해결할 수 있다.

1. 1번 배열의 모든 숫자가 각 bit가 몇 개씩 켜져 있는지를 배열에 저장한다.
2. 2번 배열의 모든 숫자를 순회하며 각 숫자에 해당하는 bit에 저장된 숫자를 더해준다.
   1. 이 값은 배열의 모든 원소쌍을 \(AND\) 연산하여 얻은 배열의 모든 수를 훑어보며 각 bit가 몇 개씩 켜져 있는지를 구한 값이 된다.
3. 해당 값을 이용하여 답을 구한다.

사실 구현 자체는 그리 어렵지 않지만 아이디어가 굉장히 재밌는 문제가 아닌가 싶다.

class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
    	vector<int> cnt1(32);
        vector<long long> cnt2(32);
    	for (auto num : arr1) {
		    int c = 0;
		    while (num) {
    			cnt1[c] += (num & 1);
    			++c;
    			num /= 2;
    		}
    	}
    	for (auto num : arr2) {
    		int c = 0;
    		while (num) {
    			if (num & 1) {
    				cnt2[c] += cnt1[c];
    			}
    			++c;
    			num /= 2;
    		}
    	}
    	int ans = 0;
    	for (int i = 0; i < cnt2.size(); ++i) 
    			ans |= ((cnt2[i] % 2) << i);
    	return ans;
    }
};

똑같은 코드를 제출해도 runtime이 200ms 가량 널뛰기를 해서 최적화는 아래 코드를 마지막으로 포기했다.

class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
    	vector<int> cnt1(32), cnt2(32);
    	for (auto& num : arr1) {
    		int c = 0;
    		while (num) {
    			cnt1[c++] += (num & 1);
    			num >>= 1;
    		}
    	}
    	for (auto& num : arr2) {
    		int c = 0;
    		while (num) {
    			cnt2[c++] += (num & 1);
    			num >>= 1;
    		}
    	}
    	int ans = 0;
    	for (int i = 0; i < cnt2.size(); ++i) 
    			ans |= ((1 & (cnt1[i] & cnt2[i])) << i);
    	return ans;
    }
};

---

마치며

Daily 문제를 풀던 중, 추천 문제에 hard 난이도 문제가 나온 것을 보고, 구경만 하고 넘어가자라는 생각으로 들어왔는데 문제를 읽자마자 아이디어가 떠올라 버려서 문제를 해결하게 되었다. Bitwise를 가지고 논게 꽤 오래라 이런 문제가 나오면 막막할 것 같은 느낌을 가지고 있었는데 이 문제를 해결하며 그런 걱정은 싹 날려버렸다.