इस लेख में, हम C++ में बिटवाइज़ OR ≥ K वाले सबअर्रे की संख्या को हल करने पर संक्षिप्त व्याख्या प्रदान करेंगे। तो हमारे पास एक सरणी arr[] और एक पूर्णांक K है, और हमें उन सबअर्रे की संख्या ढूंढनी है जिनका OR (बिटवाइज़ OR) K से अधिक या बराबर है। तो दी गई समस्या का उदाहरण यहाँ है:
Input: arr[] = {1, 2, 3} K = 3 Output: 4 सबअर्रे का बिटवाइज़ OR: {1} = 1 {1, 2} = 3 {1, 2, 3} = 3 {2} = 2 {2, 3} = 3 {3} = 3 4 सबअर्रे का बिटवाइज़ 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}; // दी गई सरणी 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) // यदि bitwise ≥ k तो answer बढ़ाएं answer++; } } cout << answer << "\n"; return 0; }आउटपुट
4
यह दृष्टिकोण बहुत सरल है, लेकिन इसकी खामियां हैं क्योंकि यह दृष्टिकोण उच्च प्रतिबंधों के लिए बहुत अच्छा नहीं है क्योंकि उच्च प्रतिबंधों के लिए, यह बहुत अधिक समय लेगा क्योंकि इस दृष्टिकोण की समय जटिलता O(N²) है जहां N दी गई सरणी का आकार है, इसलिए अब हम कुशल दृष्टिकोण के लिए जा रहे हैं।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम 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 += size - ind; } cout << answer << "\n"; return 0; }आउटपुट
4
इस दृष्टिकोण में, हम बाइनरी सर्च और सेगमेंट ट्री का उपयोग कर रहे हैं, जो हमारी समय जटिलता को O(N²) से O(Nlog(N)) तक कम करने में मदद कर रहे हैं, जो बहुत अच्छा है। अब यह प्रोग्राम पिछले वाले के विपरीत बड़े प्रतिबंधों के लिए भी काम कर सकता है।
निष्कर्ष
इस लेख में, हम बाइनरी सर्च और सेगमेंट ट्री का उपयोग करके O(nlog(n)) समय जटिलता में OR ≥ K वाले सबअर्रे की संख्या ज्ञात करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य और कुशल) भी सीखा जिससे हमने इस समस्या को हल किया। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।