এই নিবন্ধে, আমরা পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়. আমাদেরকে প্রদত্ত পরিসরে উপস্থিত সমস্ত সংখ্যার বিটওয়াইজ বা খুঁজে বের করার দায়িত্ব দেওয়া হয়েছে, উদাহরণস্বরূপ,
Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7 প্রদত্ত সমস্যাটিতে, আমরা এটিকে একটি নৃশংস শক্তি পদ্ধতির সাথে যোগাযোগ করব এবং তারপরে এটি উচ্চ সীমাবদ্ধতার জন্য কাজ করতে পারে কিনা তা পরীক্ষা করে দেখব। যদি না হয়, তাহলে আমরা উচ্চ সীমাবদ্ধতার জন্যও কাজ করার জন্য আমাদের দৃষ্টিভঙ্গি অপ্টিমাইজ করব।
ব্রুট ফোর্স অ্যাপ্রোচ
এই পদ্ধতিতে, আমরা কেবল প্রতিটি রেঞ্জের মধ্য দিয়ে অতিক্রম করতে যাচ্ছি এবং সেই পরিসরের সমস্ত সংখ্যার বিটওয়াইজ OR গণনা করব এবং আমাদের উত্তর প্রিন্ট করব।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = { 7, 5, 3, 5, 2, 3 };
int n = sizeof(arr) / sizeof(int); // size of our array
int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for(int i = 0; i < q; i++) { // traversing through all the queries
long ans = 0;
for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
ans |= arr[j]; // calculating the answer
cout << ans << "\n";
}
return 0;
} আউটপুট
7 3
এই পদ্ধতিতে O(N*Q) এর একটি সময় জটিলতা রয়েছে যেখানে N হল আমাদের অ্যারের আকার এবং Q হল প্রশ্নের সংখ্যা এখন আপনি দেখতে পাচ্ছেন, এই জটিলতা উচ্চতর সীমাবদ্ধতার জন্য কাজ করবে না, তাই এখন আমরা আমাদের পদ্ধতিকে অপ্টিমাইজ করব যেমন এটি উচ্চ সীমাবদ্ধতার জন্যও কাজ করে।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা উপসর্গ বিট সংখ্যা গণনা করব, এবং তারপরে আমরা পরীক্ষা করব যে কোন একটিতে একটি নির্দিষ্ট বিট সেট আছে কিনা। যদি হ্যাঁ, তাহলে আমরা উত্তরে এই বিটটি রাখি; অন্যথায়, আমরা এটি কিছুটা ছেড়ে দিই।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making prefix counts
for (int j = 31; j >= 0; j--) {
prefixbits[j][0] = ((arr[0] >> j) & 1);
for (int i = 1; i < n; i++) {
prefixbits[j][i] = arr[i] & (1LL << j);
prefixbits[j][i] += prefixbits[j][i - 1];
}
}
return;
}
int check(int l, int r) { // calculating the answer
long ans = 0; // to avoid overflow we are taking ans as long
for (int i = 0; i < 32; i++) {
int x;
if (l == 0)
x = prefixbits[i][r];
else
x = prefixbits[i][r] - prefixbits[i][l - 1];
if (x != 0)
ans = (ans | (1LL << i));
}
return ans;
}
int main() {
int arr[] = {7, 5, 3, 5, 2, 3};
int n = sizeof(arr) / sizeof(int); // size of our array
bitcount(arr, n);
int queries[][2] = {{1, 3}, {4, 5}}; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
cout << check(queries[i][0], queries[i][1]) << "\n";
}
return 0;
} আউটপুট
7 3
এই পদ্ধতিতে O(N) এর সময় জটিলতা রয়েছে , যেখানে N হল আমাদের অ্যারের আকার যাতে এই পদ্ধতিটি উচ্চতর সীমাবদ্ধতার জন্য কাজ করতে পারে।
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা প্রিফিক্স বিট গণনা করছি এবং এটি সংরক্ষণ করছি। এখন আমরা একটি কোয়েরি গণনা করি যা আমরা সেই প্রিফিক্স কাউন্টের মধ্য দিয়ে যাই এবং l-1 এর বিট কাউন্টগুলি সরিয়ে ফেলি যাতে আমাদের পরিসরে [l, r] সংখ্যার বিট গণনা রয়েছে এখন আমরা জানি যদি কোনো সংখ্যায় একটি বিট সেট করা থাকে। সুতরাং আপনি যদি এটিকে বিটওয়াইজ বা অন্য কোনও সংখ্যার সাথে নেন তবে বিটটি সেট থাকবে তাই বিটওয়াইজের এই বৈশিষ্ট্যটি ব্যবহার করে বা আমরা পরীক্ষা করি যে বিট গণনা শূন্য নয় তার মানে সেট বিট সহ একটি সংখ্যা রেঞ্জে উপস্থিত রয়েছে, তাই আমরা সেই বিটটি সেট করি এর উত্তর এবং লুপের মাধ্যমে চালিয়ে যান এবং অবশেষে উত্তরটি প্রিন্ট করুন।
উপসংহার
এই নিবন্ধটি প্রদত্ত অ্যারের সূচী পরিসর [L, R]-এ বিটওয়াইজ বা কোয়েরি গণনা করার জন্য একটি সমস্যার সমাধান করে। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
