এই প্রবন্ধে, আমরা C++ এ বিটওয়াইজ OR>=K আছে এমন সাবয়ারের সংখ্যা সমাধানের একটি সংক্ষিপ্ত ব্যাখ্যা প্রদান করব। সুতরাং আমাদের একটি অ্যারে অ্যারে[] এবং একটি পূর্ণসংখ্যা K আছে, এবং আমাদেরকে OR(বিটওয়াইজ বা) কে-এর থেকে বড় বা সমান সাবয়ারের সংখ্যা খুঁজে বের করতে হবে। তাই এখানে প্রদত্ত সমস্যার উদাহরণ হল -
Input: arr[] = {1, 2, 3} K = 3
Output: 4
Bitwise OR of sub-arrays:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4 sub-arrays have bitwise OR ≥ 3
Input: arr[] = {3, 4, 5} K = 6
Output: 2 সমাধান খোঁজার পন্থা
এখন আমরা C++ −
ব্যবহার করে সমস্যা সমাধানের জন্য দুটি ভিন্ন পদ্ধতি ব্যবহার করবব্রুট ফোর্স
এই পদ্ধতিতে, আমরা কেবল সমস্ত সাব্যারেগুলির মধ্য দিয়ে যেতে যাচ্ছি যেগুলি তৈরি করা যেতে পারে এবং OR কে K-এর থেকে বড় বা সমান কিনা তা পরীক্ষা করতে যাচ্ছি। যদি হ্যাঁ, তাহলে আমরা আমাদের উত্তর বৃদ্ধি করতে যাচ্ছি।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 2, 3}; // given array.
int k = 3;
int size = sizeof(arr) / sizeof(int); // the size of our array.
int answer = 0; // the counter variable.
for(int i = 0; i < size; i++){
int bitwise = 0; // the variable that we compare to k.
for(int j = i; j < size; j++){ // all the subarrays starting from i.
bitwise = bitwise | arr[j];
if(bitwise >= k) // if bitwise >= k increment answer.
answer++;
}
}
cout << answer << "\n";
return 0;
} আউটপুট
4
এই পদ্ধতিটি খুবই সহজ, তবে এর ত্রুটি রয়েছে কারণ এই পদ্ধতিটি উচ্চতর সীমাবদ্ধতার জন্য খুব ভাল নয়, উচ্চ সীমাবদ্ধতার জন্য এটি খুব বেশি সময় নিতে চলেছে কারণ এই পদ্ধতির সময় জটিলতা হল O(N*N) যেখানে N হল প্রদত্ত অ্যারের আকার তাই এখন আমরা একটি দক্ষ পদ্ধতির জন্য যাচ্ছি।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা OR অপারেটরের কিছু বৈশিষ্ট্য ব্যবহার করতে যাচ্ছি, যেটি হল আমরা আরও সংখ্যা যোগ করলেও এটি কখনই হ্রাস পায় না, তাই যদি আমরা i থেকে j পর্যন্ত একটি সাবয়ারে পাই যার OR বড় বা K এর সমান, তাই প্রতিটি সাবঅ্যারে যে পরিসীমা {i,j}-এ 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){ // segment tree building
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){ // for processing our queries or subarrays.
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}; // given array.
int k = 3;
int size = sizeof(arr) / sizeof(arr[0]); // the size of our array.
int answer = 0; // the counter variable.
build(arr, 1, 0, size - 1); // building segment tree.
for(int i = 0; i < size; i++){
int start = i, end = size-1;
int ind = INT_MAX;
while(start <= end){ // binary search
int mid = (start + end) / 2;
if(query(1, 0, size-1, i, mid) >= k){ // checking subarray.
ind = min(mid, ind);
end = mid - 1;
}
else
start = mid + 1;
}
if(ind != INT_MAX) // if ind is changed then increment the answer.
answer += size - ind;
}
cout << answer << "\n";
return 0;
} আউটপুট
4
এই পদ্ধতিতে, আমরা বাইনারি অনুসন্ধান এবং সেগমেন্ট ট্রি ব্যবহার করছি, যা আমাদের সময় জটিলতাকে O(N*N) থেকে O(Nlog(N)) কমাতে সাহায্য করছে। , যা খুব ভালো। এখন, এই প্রোগ্রামটি আগেরটির থেকে ভিন্ন, বড় সীমাবদ্ধতার জন্যও কাজ করতে পারে৷
উপসংহার
এই নিবন্ধে, আমরা বাইনারি অনুসন্ধান এবং সেগমেন্ট ট্রি ব্যবহার করে O(nlog(n)) সময়ের জটিলতায় OR>=K থাকা সাবয়ারের সংখ্যা খুঁজে পেতে একটি সমস্যার সমাধান করি। . আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আশা করি আপনি এই নিবন্ধটি সহায়ক বলে মনে করেন৷
