ในปัญหานี้ เราได้รับ arr[] และข้อความค้นหาบางรายการที่มีช่วงระหว่าง L ถึง R ในอาร์เรย์ งานของเราคือพิมพ์ XOR ของ subarray ระหว่าง L ถึง R
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − array ={1, 4, 5, 7, 2, 9} L =1 , R =5
เอาท์พุต -
คำอธิบาย − 4^5^7^2^9
-
เพื่อแก้ปัญหานี้ เราจะสร้างอาร์เรย์ตามข้อสังเกตต่อไปนี้
-
เราจะ XOR หลายบิต หากมีเลขคี่ 1 วินาที ผลลัพธ์จะเป็น 1 มิฉะนั้น ผลลัพธ์จะเป็น 0
ตอนนี้ เราจะสร้างการนับอาร์เรย์สองมิติที่จะเก็บจำนวน 1 วินาที การนับค่า[i][j] คือการนับจำนวน 1 วินาทีสำหรับตำแหน่ง i-j ซึ่งเป็นจำนวนของ 1 ที่มีอยู่ใน subarray arr[0..j] ที่ตำแหน่ง ith ของบิต พบจำนวน 1s สำหรับทุกบิตของ sub-array arr[L..R] โดยใช้อาร์เรย์การนับ สูตรหา arr[L...R] =count[i][R] - count[i][L-1] หากจำนวน 1s เป็นเลขคี่ ดังนั้น ith bit จะถูกตั้งค่าเป็นผลลัพธ์ ผลลัพธ์สุดท้ายสามารถรับได้โดยการรวมกำลังของ 2 ที่สอดคล้องกับบิต ith เนื่องจากเป็นบิตที่ตั้งค่าไว้
โปรแกรมแสดงการใช้งานโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int> >& cnt) {
int i, j;
for (i = 0; i < 32; i++) {
cnt[i][0] = 0;
for (j = 0; j < n; j++) {
if (j > 0) {
cnt[i][j] = cnt[i][j - 1];
}
if (arr[j] & (1 << i))
cnt[i][j]++;
}
}
}
int findXORofSubArray(int L, int R, const vector<vector<int> > count) {
int result = 0;
int noOfOnes;
int i, j;
for (i = 0; i < 32; i++) {
noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
if (noOfOnes & 1) {
result+=(1 << i);
}
}
return result;
}
int main(){
int arr[] = { 1, 4, 5, 7, 2, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int> > count(32, vector<int>(n));
preProcessArray(arr, n, count);
int L = 1;
int R = 5;
cout<<"The XOR of SubArray: "<<findXORofSubArray(L, R, count);
return 0;
} ผลลัพธ์
The XOR of SubArray: 13
