이 문제에서는 n개의 숫자로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 배열의 모든 하위 배열의 XOR 합을 찾는 프로그램을 만드는 것입니다.
여기에서 우리는 주어진 배열의 모든 하위 배열을 찾아야 하고 각 하위 배열에 대해 요소의 xor를 찾고 XOR 값을 합계 변수에 추가합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
Input: arr[] = {5, 1, 4}
Output:
Explanation: XOR of all subarrays for the array :
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5,1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
Sum = 5 + 1 + 4 + 4 + 5 + 0 = 19 이 문제를 해결하는 간단한 방법은 다음 for 루프를 사용하여 모든 하위 배열을 찾는 것입니다. 그런 다음 하위 배열 요소의 XOR을 찾고 합계 변수에 추가합니다.
이 솔루션은 루프 중첩을 사용하므로 효율적이지 않고 기하급수적인 시간 복잡도를 갖습니다.
이 문제를 해결하기 위한 효율적인 접근 방식은 접두사 배열을 사용하는 것입니다. 이 접두사 배열은 i까지 배열의 모든 요소에 대한 xor를 저장합니다. 즉,
prefixarr[i] = arr[0]^arr[1]^ … ^arr[i].
그런 다음 간단한 공식을 적용하여 인덱스 i에서 j까지 요소의 XOR을 찾을 수 있습니다.
XOR(i-j) = prefixarr[j] - prefixarr[i]for i >= 0. If i = 0, XOR(i-j) = prefixarr[j]
이 공식을 사용하여 모든 하위 배열의 XOR을 찾습니다.
예
솔루션의 작동을 설명하는 프로그램,
#include <iostream>
using namespace std;
int calcSubArrayXORSum(int arr[], int n) {
int sum = 0;
int multiplier = 1;
for (int i = 0; i < 30; i++) {
int oddCount = 0;
bool isOdd = 0;
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
isOdd = (!isOdd);
if (isOdd)
oddCount++;
}
for (int j = 0; j < n; j++) {
sum += (multiplier * oddCount);
if ((arr[j] & (1 << i)) > 0)
oddCount = (n - j - oddCount);
}
multiplier *= 2;
}
return sum;
}
int main() {
int arr[] = { 3, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all subarrays is "<<calcSubArrayXORSum(arr, n);
return 0;
} 출력
Sum of XOR of all subarrays is 46