मान लीजिए हमें एक सरणी 'arr' दी गई है जिसमें n क्रमबद्ध पूर्णांक मान हैं। हमें एक सरणी 'query' भी दी गई है जिसका आकार q है, और हमें बताना है कि 'query' में मान दिए गए सरणी 'arr' में मौजूद हैं या नहीं। यदि query में कोई मान arr में मौजूद है, तो हम "Present" प्रिंट करते हैं साथ ही वह स्थिति जहां मान स्थित है। अन्यथा, हम "Not present" प्रिंट करते हैं और arr में वह स्थिति प्रिंट करते हैं जहां query में मान से बड़ा न्यूनतम मान स्थित है। हमें याद रखना होगा कि सरणियां 1-इंडेक्स्ड हैं।
उदाहरण के लिए, यदि इनपुट n = 8, arr = {1, 2, 3, 4, 7, 9, 12, 15}, q = 3, query = {1, 5, 8} है, तो आउटपुट होगा:
Present 1 Not present 5 Not present 6
query का पहला मान arr में स्थिति 1 पर मौजूद है।
query का दूसरा मान arr में मौजूद नहीं है। query में मान से बड़ा न्यूनतम मान स्थिति 5 पर है।
इसी तरह, query का तीसरा मान भी arr में मौजूद नहीं है। इससे बड़ा मान arr में स्थिति 6 पर है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- एक सरणी values परिभाषित करें
- i := 0 से n-1 तक:
- arr[i] को values के अंत में डालें
- i := 0 से q-1 तक:
- idx := (values में पहला तत्व जो query[i] से कम नहीं है) की स्थिति - values में पहले तत्व की स्थिति
- यदि values[idx] query[i] के बराबर है:
- "Present " प्रिंट करें
- अन्यथा:
- "Not present " प्रिंट करें
- idx + 1 प्रिंट करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <vector> #include <iostream> using namespace std; void solve(int n, int arr[], int q, int query[]) { vector<int> values; for(int i = 0; i < n; i++){ values.push_back(arr[i]); } for(int i = 0; i < q; i++) { int idx = lower_bound (values.begin(), values.end(), query[i]) - values.begin(); if (values[idx] == query[i]) cout << "Present "; else cout << "Not present "; cout << idx + 1 << endl; } } int main() { int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15}; int query_arr[] = {1, 5, 8}; solve(8, input_arr, 3, query_arr); return 0; }इनपुट (stdin)
int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15}; int query_arr[] = {1, 5, 8}; solve(8, input_arr, 3, query_arr);आउटपुट
Present 1 Not present 5 Not present 6
