이 문제에서는 n개의 숫자로 구성된 배열 aar[]가 제공됩니다. 우리의 임무는 가능한 모든 부분 집합의 XOR 합을 찾는 프로그램을 만드는 것입니다.
여기에서 배열의 모든 하위 집합을 찾을 수 있습니다. 그런 다음 각 하위 집합에 대해 하위 집합 요소의 XOR을 찾아 합계 변수에 추가합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
Input: arr[] = {5, 1, 4}
Output: 20
Explanation: XOR of all subsets:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
Sum of XOR = 5 + 1 + 4 + 4 + 1 + 5 = 20 문제에 대한 간단한 해결책은 루프를 사용하여 배열의 가능한 모든 하위 집합을 찾은 다음 각 하위 집합에 대해 모든 요소의 XOR을 찾고 합계를 업데이트하는 것입니다. 끝에 합계를 반환합니다.
이것은 효과적인 접근 방식이 아닙니다. 값이 크면 시간 복잡도가 기하급수적으로 증가합니다.
효율적인 접근 방식은 XOR의 속성을 사용하는 것입니다. 여기에서 배열의 모든 요소의 OR을 찾고 비트를 확인합니다. i번째가 설정되면 (2^(n-1+i))로 합계를 업데이트합니다.
예시
솔루션의 작동을 설명하는 프로그램,
#include <iostream>
#include <math.h>
using namespace std;
int subSetXORSum(int arr[], int n) {
int bitOR = 0;
for (int i=0; i < n; ++i)
bitOR |= arr[i];
return (bitOR * pow(2, n-1));
}
int main() {
int arr[] = {1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all possible subsets is "<<subSetXORSum(arr, size);
} 출력
Sum of XOR of all possible subsets is 20