এই নিবন্ধে, আমরা একটি সমস্যা দিয়েছি যেখানে আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে, এবং আমাদেরকে প্রদত্ত রেঞ্জগুলির বিটওয়াইজ AND খুঁজে বের করার দায়িত্ব দেওয়া হয়েছে, উদাহরণস্বরূপ 7 মাইনাস;
Input: arr[ ] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[ ] = {{0, 1}, {3, 5}}
Output:
1
0 0
1 AND 31 = 1
23 AND 34 AND 4 = 00
Input: arr[ ] = {1, 2, 3, 4, 510, 10 , 12, 16, 8}, q[ ] = {{0, 42}, {1, 33, 4}}
Output:
0 8
0 আমরা প্রথমে ব্রুট ফোর্স পদ্ধতি প্রয়োগ করতে যাচ্ছি এবং এর সময় জটিলতা পরীক্ষা করতে যাচ্ছি। যদি আমাদের সময় জটিলতা যথেষ্ট ভাল না হয়, আমরা একটি ভাল পদ্ধতির বিকাশ করার চেষ্টা করব।
ব্রুট ফোর্স অ্যাপ্রোচ
প্রদত্ত পদ্ধতিতে, আমরা প্রদত্ত পরিসীমা অতিক্রম করব এবং আমাদের উত্তর খুঁজে বের করব এবং এটি প্রিন্ট করব।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int main() {
int ARR[] = { 10, 10 , 12, 16, 8 };
int n = sizeof(ARR) / sizeof(int); // size of our array
int queries[][2] = { {0, 2}, {3, 4} }; // 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 = 1LL << 32;
ans -= 1; // making all the bits of ans 1
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;
} আউটপুট
8 0
এই পদ্ধতিতে, আমরা প্রতিটি প্রশ্নের রেঞ্জের মাধ্যমে একটি লুপ চালাই এবং তাদের সম্মিলিত বিটওয়াইজ মুদ্রণ করি, এবং তাই আমাদের প্রোগ্রামের সামগ্রিক জটিলতা হয়ে ওঠে O(N*Q) , যেখানে N হল আমাদের অ্যারের আকার এবং Q হল এখন আমাদের প্রশ্নের সংখ্যা যেহেতু আপনি দেখতে পাচ্ছেন যে এই জটিলতা উচ্চতর সীমাবদ্ধতার জন্য উপযুক্ত নয় তাই আমরা এই সমস্যার জন্য একটি দ্রুত পদ্ধতি নিয়ে আসব৷
দক্ষ পদ্ধতি
এই সমস্যায়, প্রদত্ত রেঞ্জে সেট বিটের অবদান পরীক্ষা করে প্রদত্ত রেঞ্জের বিটওয়াইজ AND গণনা করতে আমরা অ্যারের প্রিফিক্স বিট গণনা প্রাক গণনা করি।
উদাহরণ
#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 == r - l + 1)
ans = ans | 1LL << i;
}
return ans;
}
int main() {
int ARR[] = { 10, 10 , 12, 16, 8 };
int n = sizeof(ARR) / sizeof(int); // size of our array
memset(prefixbits, 0, sizeof(prefixbits)); // initializing all the elements with 0
bitcount(ARR, n);
int queries[][2] = {{0, 2}, {3, 4}}; // 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;
} আউটপুট
2 0
এই পদ্ধতিতে, আমরা প্রশ্নগুলি গণনা করার জন্য একটি ধ্রুবক সময় নিচ্ছি যা আমাদের সময় জটিলতাকে O(N*Q) থেকে উল্লেখযোগ্যভাবে হ্রাস করে। O(N) তে , যেখানে N এখন আমাদের প্রদত্ত অ্যারের আকার। এই প্রোগ্রামটি উচ্চ সীমাবদ্ধতার জন্যও কাজ করতে পারে।
উপরের কোডের ব্যাখ্যা
n এই পদ্ধতিতে, আমরা সমস্ত প্রিফিক্স বিট গণনা করছি এবং এটিকে সূচকে সংরক্ষণ করছি। এখন যখন আমরা প্রশ্নগুলি গণনা করি, তখন আমাদের কেবলমাত্র পরিসরে উপস্থিত উপাদানগুলির সংখ্যার মতো একটি বিট একই গণনা আছে কিনা তা পরীক্ষা করতে হবে। যদি হ্যাঁ, আমরা এই বিটটিকে আমাদের x-এ 1 এ সেট করি, এবং যদি না হয়, আমরা বিটটিকে এমনভাবে ছেড়ে দিই যেন প্রদত্ত পরিসরে উপস্থিত যেকোনো সংখ্যার সেই বিটটি 0 থাকে, তাই সেই বিটের পুরো বিটওয়াইজ এবং শূন্য হবে, এবং এভাবেই আমরা বিটওয়াইজ এবং গণনা করছি।
উপসংহার
এই নিবন্ধে, আমরা বিটওয়াইজ এবং প্রদত্ত অ্যারের সূচী পরিসর [L, R] এর জন্য সমস্ত প্রশ্নের গণনা করার জন্য একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
