Trong bài toán này, chúng ta được đưa ra một mảng gồm n phần tử. Nhiệm vụ của chúng ta là in XOR của XOR tất cả các mảng con có thể có (theo thứ tự) được tạo từ các phần tử của mảng.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - mảng ={1, 3, 6, 8}
Đầu ra - 0
Giải thích -
(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6)^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)
Để giải quyết vấn đề này, một giải pháp đơn giản có thể là lặp lại trên tất cả các mảng con và tìm xors. Nhưng đây là một cách tiếp cận không hiệu quả. Một cách tiếp cận tốt hơn có thể là đếm tần suất của từng phần tử của mảng đã xảy ra trong tất cả các mảng con và sử dụng thuộc tính xor - xor của phần tử chẵn số lần là 0 . Sử dụng điều này, chúng tôi sẽ bỏ qua tất cả các giá trị xuất hiện số lần chẵn trong danh sách mảng con, bây giờ các phần tử có tần suất xuất hiện lẻ sẽ được xem xét, tức là các phần tử có tần suất xuất hiện lẻ sẽ cho kết quả cuối cùng.
Để tìm sự xuất hiện của từng phần tử của mảng trong các mảng con của nó, chúng ta sẽ sử dụng công thức này (i + 1) * (n-i) .
Sử dụng công thức này, chúng tôi sẽ tìm tần suất xuất hiện của từng phần tử và sau đó xem xét những phần tử có tần suất lẻ, xor sau đó để có kết quả cuối cùng.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#include <iostream>
using namespace std;
int xorSubarrayXors(int arr[], int N){
int result = 0;
for (int i = 0; i < N; i++){
int freqency = (i + 1) * (N - i);
if (freqency % 2 == 1)
result ^= arr[i];
}
return result;
}
int main() {
int arr[] = {1, 3, 6, 8};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The xor of all subarray xors is : "<<xorSubarrayXors(arr, N);
return 0;
} Đầu ra
The xor of all subarray xors is : 0