এই সমস্যায়, আমাদেরকে n এবং Q প্রশ্নগুলির একটি অ্যারে দেওয়া হয়েছে যার প্রতিটিতে 2 টি মান রয়েছে। আমাদের কাজ হল L-th ক্ষুদ্রতম সংখ্যা এবং এর মধ্যে পরম পার্থক্য ফেরত দেওয়ার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা। R-তম ক্ষুদ্রতম সংখ্যা।
সমস্যা বর্ণনা − প্রতিটি প্রশ্নের সমাধান করার জন্য, আমাদেরকে Lth ক্ষুদ্রতম এবং Rth ক্ষুদ্রতম সংখ্যার সূচক খুঁজে বের করতে হবে। এবং এই সূচকগুলির মধ্যে পার্থক্য খুঁজুন।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4}, {1, 5}} আউটপুট
1 2
ব্যাখ্যা
For {2, 4}: 2nd smallest element is 2 whose index is 4
4th smallest element is 5 whose index is 3 Difference = 4 - 3 = 1
For {1, 5} Smallest element is 1 whose index is 2
5th smallest element is 8 whose index is 0 Difference = 2 - 0 = 2 সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমরা একটি জোড়া তৈরি করব যা অ্যারের উপাদানগুলির সূচী এবং মান সংরক্ষণ করবে। এবং প্রতিটি প্রশ্নের L এবং R উভয় মানের জন্য i-তম ক্ষুদ্রতম উপাদানটি খুঁজুন। তারপর তাদের সূচকের পরম পার্থক্য প্রিন্ট করুন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
pair<int, int> arrayIndex[n];
for (int i = 0; i < n; i++) {
arrayIndex[i].first = arr[i];
arrayIndex[i].second = i;
}
sort(arrayIndex, arrayIndex + n);
for (int i = 0; i < Q; i++){
int result = ( abs(arrayIndex[queries[i][0] - 1].second - arrayIndex[queries[i][1] - 1].second) );
cout<<"For Query "<<(i+1)<<": Difference is "<<result<<endl;
}
}
int main() {
int arr[] = { 8, 4, 1, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
solveAllQueries(arr, n, Q, queries);
return 0;
} আউটপুট
For Query 1: Difference is 1 For Query 2: Difference is 2
এই প্রোগ্রামটি জোড়া ডেটা স্ট্রাকচার ব্যবহার করে কিন্তু একটি সমাধান আছে যা এটি ব্যবহার না করেই পার্থক্য খুঁজে পেতে পারে। এর জন্য, আমরা একটি অ্যারে ব্যবহার করব যা উপাদানগুলিকে আরোহী ক্রমে সংরক্ষণ করবে। এবং তারপর প্রতিটি প্রশ্নের জন্য L এবং R উভয় মানের জন্য ith ক্ষুদ্রতম উপাদান খুঁজে বের করা। তারপর তাদের সূচকের পার্থক্য খুঁজুন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int searchEle(int arr[], int ele, int n){
for(int i = 0; i < n; i++)
if(arr[i] == ele)
return i;
return -1;
}
int findDifference(int arr[], int minArray[], int n, int L, int R){
int Lele = minArray[L-1];
int Rele = minArray[R-1];
int index1 = searchEle(arr, Lele, n);
int index2 = searchEle(arr, Rele, n);
return abs(index1 - index2);
}
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
int minArray[n];
for (int i = 0; i < n; i++)
minArray[i] = arr[i];
sort(minArray, minArray + n);
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1)<<": Difference is "<<findDifference(arr, minArray, n, queries[i][0], queries[i][1])<<endl;
}
}
int main() {
int arr[] = { 8, 4, 1, 5, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
solveAllQueries(arr, n, Q, queries); return 0;
} আউটপুট
For Query 1: Difference is 1 For Query 2: Difference is 2
