এই আর্টিকেলে আমরা C++-এ বিটওয়াইজ OR >= K वाले সাবঅ্যারে সংখ্যা বের করার সংক্ষিপ্ত ব্যাখ্যা দিব। আমাদের কাছে একটি অ্যারে arr[] এবং একটি পূর্ণসংখ্যা K আছে, এবং আমাদের কাজ হল ওই সাবঅ্যারেগুলো খুঁজে বের করা যাদের বিটওয়াইজ OR (বিটওয়াইজ অথবা) K-এর চেয়ে বড় বা সমান। নিচে উদাহরণ দেওয়া হলো:
ইনপুট: arr[] = {1, 2, 3} K = 3
আউটপুট: 4
সাবঅ্যারেগুলোর বিটওয়াইজ OR:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4টি সাবঅ্যারের বিটওয়াইজ OR ≥ 3
ইনপুট: arr[] = {3, 4, 5} K = 6
আউটপুট: 2
সমাধানের পদ্ধতিসমূহ
C++ ব্যবহার করে এই সমস্যাটি সমাধানের জন্য আমরা দুটি ভিন্ন পদ্ধতি ব্যবহার করব:
ব্রুট ফোর্স
এই পদ্ধতিতে আমরা সকল সম্ভাব্য সাবঅ্যারে traverser করব এবং চেক করব তাদের OR >= K কিনা। হ্যাঁ হলে আউটপুট বাড়াব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main(){ int arr[] = {1, 2, 3}; // দেওয়া অ্যারে int k = 3; int size = sizeof(arr) / sizeof(int); // অ্যারের আকার int answer = 0; // কাউন্টার ভেরিয়েবল for(int i = 0; i < size; i++){ int bitwise = 0; // K-এর সাথে তুলনা করার ভেরিয়েবল for(int j = i; j < size; j++){ // i থেকে শুরু হওয়া সকল সাবঅ্যারে bitwise = bitwise | arr[j]; if(bitwise >= k) // যদি বিটওয়াইজ >= k হয় তবে answer বাড়াও answer++; } } cout << answer << "\n"; return 0; }
আউটপুট
4
এই পদ্ধতি সহজ হলেও এর ত্রুটিগুলো আছে: বড় কনস্ট্রেইন্টের জন্য এটি খুব ধীর কারণ এর সময় জটিলতা O(N²), যেখানে N হল অ্যারের আকার। তাই আমরা দক্ষ পদ্ধতির দিকে যাচ্ছি।
দক্ষ পদ্ধতি (Efficient Approach)
এই পদ্ধতিতে আমরা OR অপারেটরের একটি বৈশিষ্ট্য ব্যবহার করব: এটি কখনোই কমে না এমনকি আরও সংখ্যা যোগ করলেও। তাই যদি আমরা i থেকে j পর্যন্ত একটি সাবঅ্যারে পাই যার OR >= K, তবে সেই রেঞ্জ {i,j}-কে অন্তর্ভুক্ত করে এমন সকল সাবঅ্যারের OR-ও K-এর চেয়ে বড় হবে। আমরা এই বৈশিষ্ট্যটি ব্যবহার করে কোডটি উন্নত করব।
উদাহরণ
#include <bits/stdc++.h> #define N 1000 using namespace std; int t[4*N]; void build(int* a, int v, int start, int end){ // সেগমেন্ট ট্রি বিল্ড if(start == end){ t[v] = a[start]; return; } int mid = (start + end)/2; build(a, 2 * v, start, mid); build(a, 2 * v + 1, mid + 1, end); t[v] = t[2 * v] | t[2 * v + 1]; } int query(int v, int tl, int tr, int l, int r){ // কোয়েরি প্রসেসিং if (l > r) return 0; if(tl == l && tr == r) return t[v]; int tm = (tl + tr)/2; int q1 = query(2*v, tl, tm, l, min(tm, r)); int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r); return q1 | q2; } int main(){ int arr[] = {1, 2, 3}; // দেওয়া অ্যারে int k = 3; int size = sizeof(arr) / sizeof(arr[0]); // অ্যারের আকার int answer = 0; // কাউন্টার ভেরিয়েবল build(arr, 1, 0, size - 1); // সেগমেন্ট ট্রি বিল্ড for(int i = 0; i < size; i++){ int start = i, end = size-1; int ind = INT_MAX; while(start <= end){ // বাইনারি সার্চ int mid = (start + end) / 2; if(query(1, 0, size-1, i, mid) >= k){ // সাবঅ্যারে চেক ind = min(mid, ind); end = mid - 1; } else start = mid + 1; } if(ind != INT_MAX) // যদি ind পরিবর্তন হয় তবে answer বাড়াও answer += size - ind; } cout << answer << "\n"; return 0; }
আউটপুট
4
এই পদ্ধতিতে আমরা বাইনারি সার্চ এবং সেগমেন্ট ট্রি ব্যবহার করি, যা সময় জটিলতাকে O(N²) থেকে O(N log N)-এ নামিয়ে দিয়েছে, যা বড় কনস্ট্রেইন্টের জন্যও কার্যকর।
উপসংহার
এই আর্টিকেলে আমরা বাইনারি সার্চ এবং সেগমেন্ট ট্রি ব্যবহার করে O(N log N) সময় জটিলতায় OR >= K वाले সাবঅ্যারে সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা C++ প্রোগ্রাম এবং পূর্ণ পদ্ধতি (সাধারণ এবং দক্ষ) শিখেছি। একই প্রোগ্রাম C, Java, Python বা অন্য ভাষায় লেখা যায়। আশা করি এই আর্টিকেলটি সহায়ক হবে।
