এই আর্টিকেলে, আমাদের একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। আমাদের কাজ হচ্ছে দেওয়া রেঞ্জে থাকা সব সংখ্যার বিটওয়াইজ OR বের করা। উদাহরণস্বরূপ:
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); // আমাদের অ্যারের আকার int queries[][2] = { { 1, 3 }, { 4, 5 } }; // দেওয়া কোয়েরি int q = sizeof(queries) / sizeof(queries[0]); // কোয়েরি সংখ্যা for(int i = 0; i < q; i++) { // সব কোয়েরির মাধ্যমে ট্রাভার্স long ans = 0; for(int j = queries[i][0]; j <= queries[i][1]; j++) // রেঞ্জ ট্রাভার্স ans |= arr[j]; // উত্তর ক্যালকুলেট 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) { // প্রিফিক্স কাউন্ট তৈরি 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 != 0) ans = (ans | (1LL << i)); } return ans; } int main() { int arr[] = {7, 5, 3, 5, 2, 3}; int n = sizeof(arr) / sizeof(int); // আমাদের অ্যারের আকার bitcount(arr, n); int queries[][2] = {{1, 3}, {4, 5}}; // দেওয়া কোয়েরি 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; }
আউটপুট
7 3
এই পদ্ধতির টাইম কমপ্লেক্সিটি O(N), যেখানে N হল আমাদের অ্যারের আকার, তাই এই পদ্ধতি উচ্চ কনস্ট্রেইন্টের জন্যও কাজ করবে।
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা প্রিফিক্স বিট কাউন্ট ক্যালকুলেট করে সংরক্ষণ করি। এখন একটি কোয়েরি ক্যালকুলেট করার সময় আমরা সেই প্রিফিক্স কাউন্টের মাধ্যমে যাই এবং l-1 এর বিট কাউন্ট বিয়োগ করি যাতে আমাদের রেঞ্জ [l, r] এর সংখ্যাগুলোর বিট কাউন্ট পাওয়া যায়। এখন যেহেতু আমরা সেগুলো জানি, যদি কোনো সংখ্যার একটি বিট সেট থাকে, তবে সেটির যেকোনো অন্য সংখ্যার সাথে বিটওয়াইজ OR করলে বিটটি সেটই থাকবে। এই বিটওয়াইজ OR-এর প্রপার্টি ব্যবহার করে আমরা চেক করি যদি বিট কাউন্ট শূন্য না হয়, তবে সেটি মানে রেঞ্জে সেট বিট থাকা একটি সংখ্যা আছে, তাই আমরা উত্তরের সেই বিটটি সেট করি এবং লুপ চালিয়ে যাই এবং চূড়ান্তে উত্তর প্রিন্ট করি।
উপসংহার
এই আর্টিকেলে, আমরা দেওয়া অ্যারেতে [L, R] ইনডেক্স রেঞ্জে বিটওয়াইজ OR কোয়েরি সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ ও দক্ষ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
