এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে অ্যারে [] যা n উপাদান এবং aninteger k নিয়ে গঠিত। আমাদের কাজ হল k.
আকারের একটি সাব-অ্যারের সর্বোচ্চ XOR মান খুঁজে বের করাসমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {3, 1, 6, 2 ,7, 9} k = 3 আউটপুট
12
ব্যাখ্যা
k,
আকারের সমস্ত উপাদানের সমস্ত সাবাররে এবং xor{3, 1, 6} = 4
{1, 6, 2} = 5
{6, 2, 7} = 3
{2, 7, 9} = 12 সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল দুটি লুপ ব্যবহার করে। একটি অ্যারের উপরে পুনরাবৃত্তি করতে এবং অন্যটি সাবয়ারের সমস্ত উপাদানের XOR খুঁজে বের করতে। এবং তারপরে সর্বাধিক ফেরত দিন।
এই সমাধান ঠিক আছে কিন্তু সমস্যা সমাধানের জন্য আরও ভালো পদ্ধতি তৈরি করা যেতে পারে।
index 0. এবং তারপর অ্যারেটি পুনরাবৃত্তি করে এবং XOR-এ একটি নতুন উপাদান যোগ করা এবং প্রথমটি মুছে ফেলা। x^a^x =a.
সূত্র ব্যবহার করে মুছে ফেলা সম্ভবসুতরাং, প্রতিটি ইন্টারঅ্যাকশনের জন্য আমরা প্রথমে XOR ^ arr[i - k] সম্পাদন করব, যা শেষ সূচক + 1 থেকে বর্তমান সূচক - 1 পর্যন্ত সাবয়ারের মান দেবে।
তারপরে আমরা বর্তমান XOR পাওয়ার জন্য arr[i] সহ সাবয়ারের XOR সম্পাদন করব৷ আমরা সমস্ত XOR-এর মধ্যে সর্বাধিক মান খুঁজে বের করব এবং ফেরত দেব৷
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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;
} আউটপুট
The maximum XOR of subarray of size 3 is 12
