এই সমস্যায়, আমাদের একটি অ্যারে arr[] এবং কিছু কোয়েরি দেওয়া আছে যারা প্রতিটি তিনটি ভ্যালু L, R, এবং val নিয়ে গঠিত। আমাদের কাজ হল দেওয়া রেঞ্জে নির্দিষ্ট ডিজিট আছে কিনা চেক করার কোয়েরি সমাধান করার প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
প্রতিটি কোয়েরি সমাধান করতে, আমাদের চেক করতে হবে দেওয়া এলিমেন্ট 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, 4], সাবঅ্যারে = {8, 1, 7, 2}। ৩ এই সাবঅ্যারেতে নেই।
কোয়েরি ২: রেঞ্জ [0, 2], সাবঅ্যারে = {4, 8, 1}। ১ এই সাবঅ্যারেতে আছে।
কোয়েরি ৩: রেঞ্জ [4, 7], সাবঅ্যারে = {2, 9, 3, 5, 1}। ২ এই সাবঅ্যারেতে আছে।
সমাধান পদ্ধতি
সমস্যা সমাধানের একটি সহজ পদ্ধতি হল সাবঅ্যারে ট্রাভার্স করে দেওয়া এলিমেন্ট রেঞ্জে আছে কিনা চেক করা।
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)।
উন্নত সমাধান পদ্ধতি হতে পারে সেগমেন্ট টรี ব্যবহার করা যেটে সকল সম্ভাব্য ডিজিট (০-৯) সংরক্ষণ করা থাকবে। ডুপ্লিকেট এলিমেন্ট এড়ানোর জন্য সেট (set) ডেটা স্ট্রাকচার ব্যবহার করা হবে। এটি প্রতিটি নোডে সর্বোচ্চ ১০টি এলিমেন্ট রাখবে।
তারপর কোয়েরির জন্য, আমরা চেক করব এলিমেন্টটি দিয়া রেঞ্জে আছে কিনা।
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
