Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n số. Nhiệm vụ của chúng ta là tạo một chương trình để tìm tổng XOR của tất cả các mảng con của mảng.
Ở đây, chúng ta cần tìm tất cả các mảng con của mảng đã cho, sau đó với mỗi mảng con, chúng ta sẽ tìm xor của phần tử và thêm giá trị XOR vào biến tổng.
Hãy lấy một ví dụ để hiểu vấn đề,
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 Một phương pháp đơn giản để giải quyết vấn đề này là sử dụng vòng lặp for tiếp theo để tìm tất cả các mảng con. Sau đó, tìm XOR của các phần tử của mảng con và thêm vào biến tổng.
Giải pháp này không hiệu quả vì nó sử dụng lồng các vòng lặp và sẽ có độ phức tạp về thời gian theo cấp số nhân.
Một cách tiếp cận hiệu quả để giải quyết vấn đề này là sử dụng mảng tiền tố. Mảng tiền tố này sẽ lưu trữ xor của tất cả các phần tử của mảng cho đến i. tức là,
prefixarr[i] = arr[0]^arr[1]^ … ^arr[i].
Sau đó, chúng ta có thể áp dụng một công thức đơn giản để tìm XOR của các phần tử từ chỉ số i đến j.
XOR(i-j) = prefixarr[j] - prefixarr[i]for i >= 0. If i = 0, XOR(i-j) = prefixarr[j]
Sử dụng công thức này, chúng tôi sẽ tìm thấy XOR của tất cả các mảng con.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
Sum of XOR of all subarrays is 46