এই সমস্যায়, আমাদের Nটি রেঞ্জ [L, R] এবং Q কোয়েরি দেওয়া আছে যারা প্রতিটি একটি সংখ্যা val ধারণ করে। আমাদের কাজ হল একটি সংখ্যা Nটি L-R রেঞ্জের মাঝপথে আছে কিনা চেক করার কোয়েরি সমাধান করার প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
আমাদের Nটি [L, R] টাইপের রেঞ্জ দেওয়া আছে যেগুলো L থেকে R পর্যন্ত ইন্টিজার ভ্যালু ধারণ করে, উদাহরণস্বরূপ রেঞ্জ [3, 6] 3,4,5,6 ধারণ করে। প্রতিটি কোয়েরিতে একটি val দেওয়া থাকে যার উপস্থিতি চেক করতে হবে। প্রোগ্রামটি true ফেরত দেবে যদি val যেকোনো একটি রেঞ্জে থাকে, অন্যথায় false।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট: ranges[N] = {{2, 4}, {6,7}, {9, 12}}
Q = 3
Query = {1, 7, 10}
আউটপুট: Not Present, Present, Present
ব্যাখ্যা
কোয়েরি ১: সংখ্যা ১ কোনো রেঞ্জে নেই।
কোয়েরি ২: সংখ্যা ৭ রেঞ্জ {6, 7}-এ আছে।
কোয়েরি ৩: সংখ্যা ১০ রেঞ্জ {9, 12}-এ আছে।
সমাধান পদ্ধতি
val যেকোনো রেঞ্জে আছে কিনা চেক করতে হবে, তাই val-কে সব রেঞ্জের সাথে চেক করতে হবে। এর জন্য একটি হ্যাশম্যাপ ব্যবহার করা যেতে পারে। রেঞ্জের L এবং R আলাদা করে স্টোর করে এবং বাইনারি সার্চ অ্যালগরিদম দিয়ে সার্চ করা সমাধানটিকে সহজ করবে।
C++ প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
unordered_map<int, int> mpp;
void initialiseMap(int a[][2], int n){
for (int i = 0; i < n; i++) {
v.push_back(a[i][0]);
mpp[a[i][0]] = 1;
v.push_back(a[i][1]);
mpp[a[i][1]] = 2;
}
sort(v.begin(), v.end());
}
bool isElementPresent(int val) {
int ind = lower_bound(v.begin(), v.end(), val) - v.begin();
if (v[ind] == val)
return true;
else {
if (mpp[v[ind]] == 2)
return true;
else
return false;
}
}
int main(){
int arr[][2] = {{2, 4}, {6,7}, {9, 12}};
int n = 3;
int Q = 3;
int query[] = { 1, 7, 10 };
initialiseMap(arr, n);
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(query[i]))
cout<<": The given digit "<<query[i]<<" is present in one of the given ranges\n";
else
cout<<": The given digit "<<query[i]<<" is not present in any of the given ranges\n";
}
return 0;
}
আউটপুট
For Query 1: The given digit 1 is not present in any of the given ranges For Query 2: The given digit 7 is present in one of the given ranges For Query 3: The given digit 10 is present in one of the given ranges
