এই আর্টিকেলে, আমাদের একটি সমস্যা দেওয়া আছে যেখানে পূর্ণসংখ্যা অ্যারে দেওয়া আছে, এবং আমাদের কাজ হচ্ছে দেওয়া রেঞ্জগুলোর বিটওয়াইজ AND বের করা। উদাহরণস্বরূপ:
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); // আমাদের অ্যারের আকার int queries[][2] = { {0, 2}, {3, 4} }; // দেওয়া কোয়েরি int q = sizeof(queries) / sizeof(queries[0]); // কোয়েরি সংখ্যা for(int i = 0; i < q; i++) { // সব কোয়েরির মাধ্যমে ট্রাভার্স long ans = 1LL << 32; ans -= 1; // ans-এর সব বিট ১ করুন for(int j = queries[i][0]; j <= queries[i][1]; j++) // রেঞ্জ ট্রাভার্স ans &= ARR[j]; // উত্তর ক্যালকুলেট cout << ans << "\n"; } return 0; }
আউটপুট
8 0
এই পদ্ধতিতে, আমরা প্রতিটি কোয়েরির রেঞ্জের মাধ্যমে লুপ চালিয়ে তাদের সম্মিলিত বিটওয়াইজ AND বের করি, তাই আমাদের প্রোগ্রামের ওভারঅল কমপ্লেক্সিটি হয় 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) { // প্রিফিক্স কাউন্ট তৈরি 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) { // উত্তর ক্যালকুলেট long ans = 0; // ওভারফ্লো এড়াতে 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); // আমাদের অ্যারের আকার memset(prefixbits, 0, sizeof(prefixbits)); // সব উপাদান ০ দিয়ে ইনিশিয়ালাইজ bitcount(ARR, n); int queries[][2] = {{0, 2}, {3, 4}}; // দেওয়া কোয়েরি int q = sizeof(queries) / sizeof(queries[0]); // কোয়েরি সংখ্যা 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 হল দেওয়া অ্যারের আকার। এখন এই প্রোগ্রামটি উচ্চ কনস্ট্রেইন্টের জন্যও কাজ করবে।
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা সব প্রিফিক্স বিট কাউন্ট ক্যালকুলেট করে সূচকে সংরক্ষণ করি। এখন কোয়েরি ক্যালকুলেট করার সময় আমাদের শুধু চেক করতে হয় যে একটি বিটের কাউন্ট রেঞ্জে থাকা উপাদান সংখ্যার সমান কিনা। হ্যাঁ হলে, আমরা এই বিটকে আমাদের x-এ ১ সেট করি, এবং না হলে বিটটি ওই অবস্থায় রেখে দিই। কারণ যদি রেঞ্জে যেকোনো একটি সংখ্যার সেই বিট ০ থাকে, তবে সেই বিটের পুরো বিটওয়াইজ AND শূনย์ হয়ে যাবে, এবং এভাবেই আমরা বিটওয়াইজ AND ক্যালকুলেট করছি।
উপসংহার
এই আর্টিকেলে, আমরা দেওয়া অ্যারেতে [L, R] ইনডেক্স রেঞ্জে বিটওয়াইজ AND-এর সব কোয়েরি গণনা করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ ও দক্ষ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
