[LeetCode] 1863. Sum of All Subset XOR Totals

https://leetcode.com/problems/sum-of-all-subset-xor-totals/description/

leetcode - Sum of All Subset XOR Totals

문제 유형 : 비트마스킹

문제 난이도 : Easy

 

문제

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

• For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums. 

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

 

정수 배열 nums가 주이진다. 모든 부분집합의 전체 xor연산한 값의 합을 구해라.

중복도 따로 계산된다.

 

풀이

2^{n-1}가지 경우의 수를 대입해보는 방법이 있겠지만,

또한, 배열을 한 번만 순회할 수도 있다.

모든 숫자의 비트를 OR연산한 뒤, 2^(n-1)을 곱하는 것이다.

 

추가 설명:

이 최적화 방법이 가능한 이유는 부분집합의 XOR 합의 특성 때문입니다. 자세히 설명해 드리겠습니다.

XOR 연산의 성질:

1. 교환법칙과 결합법칙:
   • a⊕b=b⊕a
   • a⊕(b⊕c)=(a⊕b)⊕c
2. 항등원:
   • a⊕0=a
3. 자기 상쇄:
   • a⊕a=0

부분집합 XOR 합의 특성:

모든 부분집합의 XOR 합을 구할 때 각 숫자는 부분집합의 절반에서 등장합니다. 예를 들어, 배열이 [a,b,c][a,b,c]인 경우:

• [a]
• [b]
• [c]
• [a,b]
• [a,c]
• [b,c]
• [a,b,c]
• []

각 숫자는 정확히 절반의 부분집합에 포함됩니다. 예를 들어, a는 [a],[a,b],[a,c],[a,b,c][a],[a,b],[a,c],[a,b,c]에서 4번 등장합니다. 이 패턴은 모든 숫자에 대해 동일하게 적용됩니다.

따라서, 각 숫자는 2(n−1)2(n−1)번 등장하고, 이를 이용하면 전체 XOR 합을 빠르게 계산할 수 있습니다.

최적화된 접근법의 단계:

1. 모든 원소의 비트를 OR 연산으로 결합:
   • 이는 모든 숫자의 비트가 한 번이라도 1인 경우를 포함합니다.
2. 2(n−1)2(n−1)을 곱하여 최종 결과 계산:
   • 각 숫자가 2(n−1)2(n−1)번 등장하므로, OR 연산의 결과에 2(n−1)2(n−1)를 곱합니다.

 

코드

C++ - O(n * 2^n)

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        int m = 1 << n;
        for(int i = 1; i < m; i++) {
            int x = 0;
            for(int j = 0; j < n; j++) {
                if((1 << j) & i) {
                    x ^= nums[j];
                }
            }
            ans += x;
        }
        return ans;
    }
};

 

 

C++ - O(n)

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int xor_sum = 0;
        for (int num : nums) {
            xor_sum |= num;
        }
        int n = nums.size();
        return xor_sum * (1 << (n - 1));
    }
};