Trong bài toán này, chúng ta được cung cấp một arr [] và một số truy vấn nằm trong khoảng từ L đến R trong mảng. Nhiệm vụ của chúng ta là in XOR của mảng con giữa L đến R.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - mảng ={1, 4, 5, 7, 2, 9} L =1, R =5
Đầu ra -
Giải thích - 4 ^ 5 ^ 7 ^ 2 ^ 9
-
Để giải quyết vấn đề này, chúng tôi sẽ tạo một mảng, dựa trên quan sát sau đây,
-
Chúng ta sẽ XOR nhiều bit, nếu có số lẻ là 1 thì kết quả sẽ là 1, ngược lại kết quả là 0.
Bây giờ, chúng ta sẽ tạo một số mảng hai chiều sẽ lưu trữ số lượng 1s. Giá trị đếm [i] [j] là số đếm số 1 cho vị trí i-j là số lượng giá trị 1 có mặt trong mảng con arr [0..j] tại vị trí thứ i của bit. Số 1 cho tất cả các bit của mảng con arr [L..R] được tìm thấy bằng cách sử dụng mảng đếm. Công thức tìm arr [L ... R] =count [i] [R] - count [i] [L-1]. Nếu số 1 là số lẻ, thì kết quả là bit thứ i được đặt. Kết quả cuối cùng có thể thu được bằng cách tính tổng lũy thừa của 2 tương ứng với bit thứ i cho rằng nó là bit đặt.
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The XOR of SubArray: 13