Để tính toán XOR của tất cả các mảng con có trong phạm vi đã cho và in nó. Ví dụ
Input : arr[] = { 4, 1, 2, 3, 5 }, Q = 3
Queries
q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }
Output : 0
2
0
Explanation : As the given problem states that we need to find XOR of all the subarrays present in the given range so as for query 2 the subarrays are :
{1}, {2}, {3}, {1, 2}, {2, 3}, (1, 2, 3}
So as you can see the number of occurrences of elements are :
1 is present 3 times
2 is present 4 times
3 is present 3 times
Now as we know the property of XOR is that the numbers that are present an even number of times get canceled out so out 2 got canceled out and just the XOR of 3 and 1 remained and that was our answer. Chúng ta cần quan sát mô hình được hình thành trong vấn đề này và sau đó chúng ta cần triển khai nó cho phù hợp.
Phương pháp tiếp cận để tìm giải pháp
Trong vấn đề này, chúng tôi đang cố gắng tìm ra các mẫu ở giữa có trong vấn đề. Khi nào. Khi chúng tôi thấy mô hình đó, chúng tôi triển khai nó cho phù hợp và kiểm tra kết quả.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r){
if ((r - l + 1) % 2 == 0) // if number of element present in the range is even
cout << "0";
else{
if (l % 2 == 0) // if l is even
cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
else // if l is odd
cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
}
}
int main(){
int arr[] = {4, 1, 2, 3, 5};
int n = sizeof(arr) / sizeof(int); // size of our array
int l[] = {1, 2, 1}; // given queries' left index
int r[] = {2, 4, 4}; // given queries' right index
int q = sizeof(l) / sizeof(int); // number of queries asked
int prefodd[n] = {0}, prefeven[n] = {0}; // different prefix xor for even and odd indices
for (int i = 1; i <= n; i++){
if ((i) % 2 == 0){ // if i is even then we change prefeven
prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
prefodd[i] = prefodd[i - 1];
}else{
prefeven[i] = prefeven[i - 1];
prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
}
}
for (int i = 0; i < q; i++){
ansQueries(prefeven, prefodd, l[i], r[i]);
}
return 0;
} Đầu ra
02 0
Giải thích về Quy tắc trên
Trong cách tiếp cận này, trước tiên chúng ta quan sát thấy rằng nếu kích thước phạm vi của chúng ta là chẵn thì câu trả lời của chúng ta sẽ bằng 0 vì mọi số xuất hiện chẵn lần khi chúng ta in tất cả các mảng con, vì vậy bằng cách lấy XOR của chúng, câu trả lời đơn giản sẽ là 0 bây giờ cho phần tiếp theo của chúng ta trong đó kích thước của phạm vi là số lẻ trong trường hợp này số xuất hiện lần lẻ ở vị trí chẵn trong phạm vi đã cho và câu trả lời của chúng tôi sẽ chỉ đơn giản là XOR của các số xuất hiện ở vị trí chẵn trong phạm vi hai đã cho, chúng tôi duy trì hai tiền tố mảng có chứa XOR của các vị trí thay thế vì lớp thích hợp của chúng ta chứa XOR của tất cả các chỉ số chẵn và prefodd chứa XOR của tất cả các chỉ số lẻ, bây giờ khi chúng ta giải quyết một truy vấn, chúng ta chỉ cần kiểm tra xem l của chúng ta là chẵn hay lẻ và đưa ra câu trả lời của chúng ta cho phù hợp .
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để giải quyết các Truy vấn trên XOR của XOR của tất cả các mảng con. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.