N পূর্ণসংখ্যার একটি অ্যারে এবং রেঞ্জের Q প্রশ্ন দেওয়া হয়েছে। প্রতিটি প্রশ্নের জন্য, আমাদের পরিসরের প্রতিটি সংখ্যার সবচেয়ে বড় বিজোড় ভাজকের XOR ফেরত দিতে হবে।
সর্বশ্রেষ্ঠ বিজোড় ভাজক হল সর্বশ্রেষ্ঠ বিজোড় সংখ্যা যা N সংখ্যাকে ভাগ করতে পারে, যেমন . 6-এর সর্বশ্রেষ্ঠ বিজোড় ভাজক হল 3, উদাহরণস্বরূপ।
Input: nums[ ] = { 3, 6, 7, 10 }, query[ ] = { { 0, 2 }, { 1, 3 } }
Output:
query1: 7
query2: 1
Explanation: greatest odd divisors of nums array are { 3, 3, 7, 5 }.
For query 1 we need to find the XOR of indexes 0, 1, and 2 which is 7, and for query2 we need to find XOR of indexes 1, 2, and 3 which is 1. সমাধান খোঁজার পদ্ধতি
সরল পদ্ধতি
প্রথমত, সহজ পদ্ধতিতে, আমাদের সমস্ত অ্যারের উপাদানগুলির সর্বশ্রেষ্ঠ বিজোড় ভাজক খুঁজে বের করতে হবে। তারপর কোয়েরির রেঞ্জ অনুযায়ী, আমাদের রেঞ্জের প্রতিটি উপাদানের XOR গণনা করতে হবে এবং রিটার্ন করতে হবে।
দক্ষ পদ্ধতি
এই সমস্যাটি সমাধান করার একটি কার্যকর উপায় হল প্রতিবার পরিসরে প্রতিটি সংখ্যার XOR খুঁজে বের করার পরিবর্তে সবচেয়ে বড় বিজোড় ভাজক সংখ্যা সম্বলিত অ্যারের একটি উপসর্গ XOR অ্যারে উপসর্গ_XOR[] তৈরি করা এবং উপসর্গ_XOR[R] - prefix_XOR[L-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];
// creating an array
// containing Greatest odd divisor of each element.
for (int i = 0; i < n; i++) {
while (nums[i] % 2 != 1)
nums[i] /= 2;
prefix_XOR[i] = nums[i];
}
// changing prefix_XOR array to prefix xor array.
for (int i = 1; i < n; i++)
prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];
// query array to find result of these queries.
int query[2][2] = {{0, 2},{1, 3}};
int q = sizeof(query) / sizeof(query[0]);
// finding results of queries.
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[0][1]] ^ prefix_XOR[query[i][0] - 1];
cout << result << endl;
}
}
return 0;
} আউটপুট
7 4
উপরের কোডের ব্যাখ্যা
-
prefix_XOR অ্যারে তৈরি করা হয় প্রতিটি উপাদানের সবচেয়ে বড় বিজোড় ভাজক সংরক্ষণ করার জন্য এবং তারপর এই অ্যারেটিকে উপসর্গ XOR অ্যারেতে পরিবর্তন করে।
-
সর্বশ্রেষ্ঠ বিজোড় ভাজককে দুই দ্বারা ভাগ করে গণনা করা হয় যতক্ষণ না এটি মডুলো 2 1 দেয়।
-
প্রিফিক্স xor অ্যারে অ্যারের মধ্য দিয়ে অতিক্রম করে এবং পূর্ববর্তী উপাদানের সাথে বর্তমান উপাদানটির বিটওয়াইজ XOR করে তৈরি করা হয়।
-
একটি প্রশ্নের ফলাফল প্রিফিক্স_XOR[] অ্যারের (বাম - 1) সূচকের সাথে উপসর্গ_XOR[] অ্যারের ডান সূচক বিয়োগ করে গণনা করা হয়।
উপসংহার
এই টিউটোরিয়ালে, আমরা একটি সমস্যা নিয়ে আলোচনা করেছি যেখানে আমাদের প্রদত্ত অ্যারের পরিসরে প্রতিটি সংখ্যার সবচেয়ে বড় বিজোড় ভাজকের XOR খুঁজে বের করতে হবে। আমরা প্রতিটি উপাদানের সর্বশ্রেষ্ঠ বিজোড় ভাজক খুঁজে বের করে এবং প্রিফিক্স xor অ্যারে ব্যবহার করে এই সমস্যাটি সমাধান করার একটি পদ্ধতি নিয়ে আলোচনা করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম নিয়েও আলোচনা করেছি যা আমরা সি, জাভা, পাইথন ইত্যাদি প্রোগ্রামিং ল্যাঙ্গুয়েজ দিয়ে করতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে।
