इस समस्या में, हमने एक सरणी एआर [] और कुछ प्रश्न दिए हैं जिनमें से प्रत्येक में तीन मान, एल और आर, और वैल शामिल हैं। हमारा काम यह जांचने के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है कि दिया गया अंक C++ में दिए गए रेंज में मौजूद है या नहीं।
समस्या का विवरण-
प्रत्येक प्रश्न को हल करने के लिए, हमें यह जांचना होगा कि दिया गया तत्व वैल एल और आर के बीच दिए गए रेंज में मौजूद है या नहीं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :arr[] ={4, 8, 1, 7, 2, 9, 3, 5, 1}
क्यू =3
क्वेरी ={{1, 4, 3}, {0, 2, 1}, {4, 7, 2}}
आउटपुट :मौजूद नहीं है
वर्तमान
वर्तमान
स्पष्टीकरण
प्रश्न 1:श्रेणी [1, 4], सबरे ={8, 1, 7, 2} है। 3 इस उप-सरणी में मौजूद नहीं है।
प्रश्न 2:श्रेणी [0, 2] है, सबरे ={4, 8, 1}। 1 इस उप-सरणी में मौजूद है।
प्रश्न 1:श्रेणी [4, 7], सबरे ={2, 9, 3, 5, 1} है। 2 इस उप-सरणी में मौजूद है।
समाधान दृष्टिकोण
समस्या को हल करने का एक आसान तरीका सबएरे को पार करना और यह जांचना है कि दिया गया तत्व सीमा में मौजूद है या नहीं।
उदाहरण
#include <iostream>
using namespace std;
bool isElementPresent(int arr[], int L, int R, int val){
for(int i = L; i <= R; i++ ){
if(arr[i] == val){
return true;
}
}
return false;
}
int main(){
int arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1};
int Q = 3;
int query[Q][3] = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }};
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(arr, query[i][0], query[i][1], query[i][2]))
cout<<": The given digit "<<query[i][2]<<" is present in the given range\n";
else
cout<<": The given digit "<<query[i][2]<<" is not present in the given range\n";
}
return 0;
} आउटपुट
For Query 1: The given digit 3 is not present in the given range For Query 2: The given digit 1 is present in the given range For Query 3: The given digit 2 is present in the given range
यह दृष्टिकोण एक लूप का उपयोग करता है, इसलिए ऑर्डर ओ (क्यू * एन) की समय जटिलता है। जहां Q प्रश्नों की संख्या है।
एक बेहतर समाधान दृष्टिकोण सभी संभावित अंकों (0 - 9) को स्टोर करने के लिए सेगमेंट ट्री का उपयोग कर सकता है। नोड में डुप्लिकेट तत्वों से बचने के लिए हम सेट डेटा संरचना का उपयोग करेंगे (इसमें डुप्लिकेट तत्वों को खत्म करने की संपत्ति है)। यह हमें प्रत्येक नोड में तत्वों की कुल संख्या को अधिकतम 10 तक कम करने में मदद करेगा।
फिर, क्वेरी के लिए, हम जांचेंगे कि दी गई सीमा में तत्व मौजूद है या नहीं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
set<int> SegTree[36];
void buildSegmentTree(int* arr, int index, int start, int end) {
if (start == end) {
SegTree[index].insert(arr[start]);
return;
}
int middleEle = (start + end) >> 1;
buildSegmentTree(arr, 2 * index, start, middleEle);
buildSegmentTree(arr, 2 * index + 1, middleEle + 1, end);
for (auto it : SegTree[2 * index])
SegTree[index].insert(it);
for (auto it : SegTree[2 * index + 1])
SegTree[index].insert(it);
}
bool isElementPresent(int index, int start, int end, int L, int R, int val){
if (L <= start && end <= R) {
if (SegTree[index].count(val) != 0) {
return true;
}
else
return false;
}
if (R < start || end < L) {
return false;
}
int middleEle = (start + end) >> 1;
bool isPresentInLeftSubArray = isElementPresent((2 * index), start,middleEle, L, R, val);
bool isPresentInRightSubArray = isElementPresent((2 * index + 1),(middleEle + 1), end, L, R, val);
return isPresentInLeftSubArray or isPresentInRightSubArray;
}
int main(){
int arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1};
int n = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[Q][3] = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }};
buildSegmentTree(arr, 1, 0, (n - 1));
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(1, 0, (n - 1), query[i][0], query[i][1], query[i][2]))
cout<<": The given digit "<<query[i][2]<<" is present in the given
range\n";
else
cout<<": The given digit "<<query[i][2]<<" is not present in the given range\n";
}
return 0;
} आउटपुट
For Query 1: The given digit 3 is not present in the given range For Query 2: The given digit 1 is present in the given range For Query 3: The given digit 2 is present in the given range