এই সমস্যাটিতে, আমরা একটি অ্যারে arr[] এবং কিছু প্রশ্ন দিয়েছি যার প্রতিটিতে তিনটি মান, L এবং R এবং val রয়েছে। আমাদের কাজ হল একটি প্রদত্ত ডিজিট C++ এ প্রদত্ত রেঞ্জে উপস্থিত আছে কিনা তা পরীক্ষা করার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা−
প্রতিটি প্রশ্নের সমাধান করার জন্য, আমাদের পরীক্ষা করতে হবে যে প্রদত্ত এলিমেন্ট ভ্যালটি L এবং R-এর মধ্যে প্রদত্ত পরিসরে উপস্থিত আছে কি না।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট :arr[] ={4, 8, 1, 7, 2, 9, 3, 5, 1}
প্রশ্ন =3
প্রশ্ন ={{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }}
আউটপুট :উপস্থিত নয়
উপস্থাপন করুন
উপস্থাপন করুন
ব্যাখ্যা
ক্যোয়ারী 1:ব্যাপ্তি হল [1, 4], subarray ={8, 1, 7, 2}। 3 এই সাব্যারেতে উপস্থিত নেই৷
৷ক্যোয়ারী 2:পরিসর হল [0, 2], subarray ={4, 8, 1}। 1 এই সাব্যারেতে উপস্থিত।
ক্যোয়ারী 1:ব্যাপ্তি হল [4, 7], subarray ={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
এই পদ্ধতিটি একটি লুপ ব্যবহার করে, তাই ক্রম O(Q * N) এর একটি সময় জটিলতা রয়েছে। যেখানে 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
