Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n phần tử và k aninteger. Nhiệm vụ của chúng ta là tìm giá trị XOR tối đa của một mảng con có kích thước k.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {3, 1, 6, 2 ,7, 9} k = 3 Đầu ra
12
Giải thích
Tất cả mảng con và xor của tất cả phần tử có kích thước k,
{3, 1, 6} = 4
{1, 6, 2} = 5
{6, 2, 7} = 3
{2, 7, 9} = 12 Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng hai vòng lặp. Một để lặp qua mảng và một để tìm XOR của tất cả các phần tử của mảng con. Và sau đó quay trở lại mức tối đa của tất cả.
Giải pháp này không sao cả nhưng có thể tạo ra một cách tiếp cận tốt hơn để giải quyết vấn đề. Chúng ta cần tìm tổng bằng cách bắt đầu từ mảng con có kích thước k bắt đầu từ
chỉ số 0. Và sau đó lặp lại mảng và thêm một phần tử mới vào XOR và xóa phần tử đầu tiên. Có thể xóa bằng cách sử dụng công thức x ^ a ^ x =a.
Vì vậy, đối với mỗi tương tác, chúng tôi sẽ thực hiện đầu tiên, XOR ^ arr [i - k], sẽ cung cấp giá trị của mảng con từ chỉ mục cuối cùng + 1 đến chỉ mục hiện tại - 1.
Sau đó, chúng tôi sẽ thực hiện XOR của mảng con với arr [i], để có được XOR hiện tại. Chúng tôi sẽ tìm và trả về giá trị lớn nhất trong số tất cả các XOR.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include<iostream>
using namespace std;
int findMaxSubArrayXOR(int arr[] , int n , int k) {
int currentXORVal = 0 ;
for (int i = 0 ; i < k ; i++)
currentXORVal = currentXORVal ^ arr[i];
int maxXor = currentXORVal;
for (int i = k ; i < n; i++) {
currentXORVal = currentXORVal ^ arr[i-k];
currentXORVal = currentXORVal ^ arr[i];
maxXor = max(maxXor, currentXORVal);
}
return maxXor;
}
int main() {
int arr[] = {3, 1, 6, 2, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout<<"The maximum XOR of subarray of size "<<k<<" is "<<findMaxSubArrayXOR(arr, n, k);
return 0;
} Đầu ra
The maximum XOR of subarray of size 3 is 12