একটি N পূর্ণসংখ্যার অ্যারে এবং রেঞ্জের Q কোয়ারী দেওয়া আছে। প্রতিটি কোয়ারীর জন্য, আমাদের রেঞ্জের প্রতিটি সংখ্যার সবচেয়ে বড় বিজোড় ভাজকের XOR ফেরত দিতে হবে।
সবচেয়ে বড় বিজোড় ভাজক হল সেই সর্বোচ্চ বিজোড় সংখ্যা যা সংখ্যা N কে ভাগ করতে পারে। উদাহরণস্বরূপ, ৬-এর সবচেয়ে বড় বিজোড় ভাজক হল ৩।
ইনপুট: nums[] = { 3, 6, 7, 10 }, query[] = { { 0, 2 }, { 1, 3 } }
আউটপুট: কোয়ারী১: 7, কোয়ারী২: 1
ব্যাখ্যা: nums অ্যারেতে সবচেয়ে বড় বিজোড় ভাজকগুলো হল { 3, 3, 7, 5 }।
কোয়ারী ১-এ আমরা ইনডেক্স ০, ১, এবং ২-এর XOR বের করব যা ৭, এবং কোয়ারী ২-এ ইনডেক্স ১, ২, এবং ৩-এর XOR হবে ১।
প্রথমে সহজ পদ্ধতিতে, আমাদের অ্যারেতে সব উপাদানের সবচেয়ে বড় বিজোড় ভাজক বের করতে হবে। তারপর কোয়ারীর রেঞ্জ অনুযায়ী, সেই রেঞ্জের প্রতিটি উপাদানের XOR গণনা করে ফেরত দিতে হবে।
এই সমস্যা সমাধানের একটি দক্ষ উপায় হল প্রিফিক্স XOR অ্যারে (prefix_XOR[]) তৈরি করা, যেখানে অ্যারেতে প্রতিটি উপাদানের জায়গায় তার সবচেয়ে বড় বিজোড় ভাজক রাখা হবে। এরপর প্রতিবার রেঞ্জের XOR বের না করে, আমরা prefix_XOR[R] XOR prefix_XOR[L-1] ব্যবহার করে O(1) সময়ে উত্তর পেতে পারি।
প্রিফিক্স XOR অ্যারে হল এমন একটি অ্যারে যেখানে প্রতিটি উপাদানে তার আগের সব উপাদানের XOR থাকে।
#include <bits/stdc++.h> using namespace std; int main(){ int nums[] = { 3, 6, 7, 10 }; int n = sizeof(nums) / sizeof(nums[0]); int prefix_XOR[n]; // প্রতিটি উপাদানের সবচেয়ে বড় বিজোড় ভাজক ধারণকারী অ্যারে তৈরি for (int i = 0; i < n; i++) { while (nums[i] % 2 != 1) nums[i] /= 2; prefix_XOR[i] = nums[i]; } // prefix_XOR অ্যারেকে প্রিফিক্স XOR অ্যারেতে রূপান্তর for (int i = 1; i < n; i++) prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i]; // কোয়ারী অ্যারে int query[2][2] = {{0, 2},{1, 3}}; int q = sizeof(query) / sizeof(query[0]); // কোয়ারীদের ফলাফল বের করা for(int i = 0; i < q; i++){ if (query[i][0] == 0) cout << prefix_XOR[query[i][1]] << endl; else { int result = prefix_XOR[query[i][1]] ^ prefix_XOR[query[i][0] - 1]; cout << result << endl; } } return 0; }
7 1
prefix_XOR অ্যারে তৈরি করা হয়েছে প্রতিটি উপাদানের সবচেয়ে বড় বিজোড় ভাজক সংরক্ষণ করার জন্য, তারপর এটি প্রিফিক্স XOR অ্যারেতে রূপান্তর করা হয়েছে।
সবচেয়ে বড় বিজোড় ভাজক বের করতে সংখ্যাকে ২ দিয়ে ভাগ করা হয়েছে যতক্ষণ না মডুলো ২ এর ফলাফল ১ আসে।
প্রিফিক্স XOR অ্যারে তৈরি করা হয়েছে অ্যারেটি ট্রাভার্স করে বর্তমান উপাদানকে পূর্ববর্তী উপাদানের সাথে বিটওয়াইজ XOR করে।
কোয়ারীর ফলাফল বের করা হয়েছে prefix_XOR[R] XOR prefix_XOR[L-1] ব্যবহার করে।
এই টিউটোরিয়ালে আমরা একটি সমস্যা নিয়ে আলোচনা করেছি যেখানে একটি অ্যারের দেওয়া রেঞ্জের প্রতিটি সংখ্যার সবচেয়ে বড় বিজোড় ভাজকের XOR বের করতে হয়। আমরা এই সমস্যা সমাধানের পদ্ধতি নিয়ে আলোচনা করেছি যেখানে প্রতিটি উপাদানের সবচেয়ে বড় বিজোড় ভাজক বের করে প্রিফিক্স XOR অ্যারে ব্যবহার করা হয়েছে। আমরা C++ প্রোগ্রামও দেখেছি যা অন্যান্য প্রোগ্রামিং ভাষা যেমন C, Java, Python-এও করা যাবে। আশা করি আপনি এই আর্টিকেলটি সহায়ক পাবেন।
