इस समस्या में, हमें एक ऐरे arr[] और कुछ क्वेरी दी गई हैं जिनमें प्रत्येक में तीन मान होते हैं, L, R, और val। हमारा कार्य C++ में दी गई रेंज में दिए गए अंक की उपस्थिति जांचने की क्वेरी को हल करने के लिए एक प्रोग्राम बनाना है।
समस्या विवरण
प्रत्येक क्वेरी को हल करने के लिए, हमें यह जांचना होगा कि दिया गया तत्व val दी गई रेंज L और R के बीच मौजूद है या नहीं।
उदाहरण से समझते हैं
इनपुट: arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1}
Q = 3
query = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }}
आउटपुट: Not Present, Present, Present
व्याख्या
क्वेरी 1: रेंज [1, 4] है, सबएरे = {8, 1, 7, 2}। इस सबएरे में 3 मौजूद नहीं है।
क्वेरी 2: रेंज [0, 2] है, सबएरे = {4, 8, 1}। इस सबएरे में 1 मौजूद है।
क्वेरी 3: रेंज [4, 7] है, सबएरे = {2, 9, 3, 5, 1}। इस सबएरे में 2 मौजूद है।
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल तरीका सबएरे को ट्रैवर्स करना और जांचना है कि दिया गया तत्व रेंज में मौजूद है या नहीं।
C++ प्रोग्राम उदाहरण (सरल दृष्टिकोण)
#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
यह दृष्टिकोण एक लूप का उपयोग करता है, इसलिए इसकी समय जटिलता O(Q * N) क्रम की है। जहां Q क्वेरी की संख्या है।
बेहतर समाधान दृष्टिकोण: सेगमेंट ट्री
एक बेहतर समाधान दृष्टिकोण सेगमेंट ट्री का उपयोग करके सभी संभावित अंकों (0-9) को स्टोर करना हो सकता है। नोड में डुप्लिकेट तत्वों से बचने के लिए हम सेट डेटा संरचना का उपयोग करेंगे (इसमें डुप्लिकेट तत्वों को खत्म करने का गुण होता है)। यह प्रत्येक नोड में तत्वों की कुल संख्या को अधिकतम 10 तक कम करने में मदद करेगा।
फिर, क्वेरी के लिए, हम जांचेंगे कि दिया गया तत्व दी गई रेंज में मौजूद है या नहीं।
C++ प्रोग्राम उदाहरण (कुशल दृष्टिकोण: सेगमेंट ट्री)
#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
