Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

C++ में दिए गए रेंज में दिया गया अंक मौजूद है या नहीं, यह जांचने के लिए प्रश्न

इस समस्या में, हमने एक सरणी एआर [] और कुछ प्रश्न दिए हैं जिनमें से प्रत्येक में तीन मान, एल और आर, और वैल शामिल हैं। हमारा काम यह जांचने के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है कि दिया गया अंक 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

  1. C++ प्रोग्राम यह जांचने के लिए कि दी गई निर्भरता से सभी कार्यों को पूरा करना संभव है या नहीं

    इस लेख में, हम यह जांचने के लिए एक कार्यक्रम पर चर्चा करेंगे कि क्या दिए गए सभी कार्यों को दिए गए पूर्वापेक्षाओं के आधार पर पूरा करना संभव है। उदाहरण के लिए, मान लें कि हमें तीन कार्य दिए गए हैं और पूर्वापेक्षाएँ हैं [[1, 0], [2, 1], [3, 2]]। ( [1,0] का मतलब है कि 1 टास्क लेने के लिए 0 टास्क पहले

  1. अद्यतन के बिना श्रेणी योग प्रश्नों के लिए सी ++ कार्यक्रम?

    हमें अनुक्रमणिका i से अनुक्रमणिका j तक के तत्वों के योग की गणना करने की आवश्यकता है। i और j इंडेक्स मानों वाली क्वेरी को कई बार निष्पादित किया जाएगा। Input:arr[] = {5, 6, 3, 4, 1 } i = 1, j =3 Output: 13 स्पष्टीकरण 6 + 3 + 4 = 13 sum[] = {5, 6+5, 3+6+5, 4+3+6+5, 1+4+3+6+5 } sum[]={5,11,14,18,19}

  1. C++ प्रोग्राम यह जांचने के लिए कि दिए गए ग्राफ में हैमिल्टनियन साइकिल या पथ मौजूद है या नहीं

    एक हैमिल्टनियन चक्र एक हैमिल्टनियन पथ है जैसे कि अंतिम शीर्ष से हैमिल्टनियन पथ के पहले शीर्ष तक एक किनारा (ग्राफ में) होता है। यह एक अप्रत्यक्ष ग्राफ़ में एक पथ है जो ग्राफ़ के प्रत्येक शीर्ष पर ठीक एक बार जाता है। कार्य और उद्देश्य: Begin    1.function isSafe() is used to check for whethe