এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে n সংখ্যক উপাদান এবং একটি পূর্ণসংখ্যা 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 বের করতে। তারপর সবার মধ্যে সর্বোচ্চটা ফেরত দেয়া।
এটি ঠিক আছে কিন্তু একটি আরও ভাল পদ্ধতি হতে পারে। আমরা ইনডেক্স ০ থেকে k আকারের সাবঅ্যারে দিয়ে শুরু করব। তারপর অ্যারে ইটারেট করে নতুন এলিমেন্ট XOR-এ যোগ করব এবং পুরনো এলিমেন্টটা বাদ দিব। XOR-এ ডিলিশন সম্ভব কারণ x^a^x = a।
প্রতিটি ইটারেশনে আমরা প্রথমে XOR ^ arr[i - k] করব, যা লাস্ট ইনডেক্স + 1 থেকে করেন্ট ইনডেক্স - 1 পর্যন্ত সাবঅ্যারে এর মান দিবে। তারপর করেন্ট XOR পাওয়ার জন্য arr[i] দিয়ে XOR করব। সব XOR-এর মধ্যে সর্বোচ্চ মান বের করে ফেরত দিব।
C++ প্রোগ্রাম উদাহরণ
#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
