इस लेख में, हम C++ में बिटवाइज़ OR>=K वाले सबएरे की संख्या को हल करने के बारे में एक संक्षिप्त विवरण प्रदान करेंगे। तो हमारे पास एक सरणी arr[] और एक पूर्णांक K है, और हमें उन उप-सरणीयों की संख्या ज्ञात करनी है जिनमें OR(bitwise या) K से अधिक या उसके बराबर है। तो यहां दी गई समस्या का उदाहरण है -
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 तक एक उप-सरणी मिलती है जिसमें 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++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।