এই সমস্যায়, আমাদেরকে একটি ম্যাট্রিক্স পরিসীমা [N][2] এবং একটি পূর্ণসংখ্যার মান k হিসাবে অন্তর L - R এর মধ্যে পূর্ণসংখ্যার মানের একটি N পরিসর দেওয়া হয়েছে। আমাদের কাজ হল প্রদত্ত এন রেঞ্জ দ্বারা উত্পন্ন সিরিজে kth উপাদান খুঁজে পাওয়া .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : ranges[][] = {{1, 3}, {5, 7}}, k = 4
Output : 5 ব্যাখ্যা −
The series is {1, 2, 3, 5, 6, 7}
The 4th element is 5. সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল প্রদত্ত রেঞ্জের জন্য পূর্ণসংখ্যার একটি সিরিজ তৈরি করা এবং তারপর তাদের অ্যারের সূচক k-তে উপাদানগুলি সন্ধান করা৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
int rangeVal[10000];
int rangeSize = 0;
for(int i = 0; i < n; i++){
for(int j = range[i][0]; j <= range[i][1]; j++){
rangeVal[rangeSize] = j;
rangeSize++;
}
}
return rangeVal[k-1];
}
int main(){
int L[] = { 1, 5 };
int R[] = { 3, 8 };
int range[][2] = {{1, 3}, {5, 8}};
int n = sizeof(L) / sizeof(int);
int k = 4;
cout<<k<<"-th element of the series generated by ranges is "<<
findKthSmallestEleSeries(n, k, range);
return 0;
} আউটপুট
4-th element of the series generated by ranges is 5
এই পদ্ধতিটি ভাল কিন্তু রেঞ্জগুলি খুব বড় হলে মেমরির সমস্যা হতে পারে। তাই, অ্যারের সমস্ত উপাদান সংরক্ষণ করার জন্য আমাদের একটি আরও ভাল পদ্ধতি বের করতে হবে।
অন্য পদ্ধতি
সমস্যা সমাধানের আরেকটি পদ্ধতি হল বাইনারি অনুসন্ধান এবং কাউন্টার অ্যারে ব্যবহার করে। কাউন্টার অ্যারে প্রদত্ত পরিসর পর্যন্ত পূর্ণসংখ্যার গণনা সংরক্ষণ করবে, কাউন্ট[i] =i-তম পরিসর পর্যন্ত অক্ষরের গণনা।
তারপর k-এর জন্য, আমরা পরিসীমা সংখ্যা i খুঁজে পাব, যেখানে k-th ক্ষুদ্রতম মান রয়েছে।
তারপর আমরা এই পরিসরে মান খুঁজে পাব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
int start = 1;
int end = n;
int count[n + 1];
count[0] = 0;
for (int i = 0; i < n; i++)
count[i + 1] = count[i] + (range[i][1] - range[i][0]) + 1;
int index = -1;
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (count[mid] > k) {
index = mid;
end = mid - 1;
}
else if (count[mid] < k)
start = mid + 1;
else {
index = mid;
break;
}
}
start = range[index - 1][0];
end = range[index - 1][1];
int indexK = k - count[index - 1];
while (start <= end) {
mid = (start + end) / 2;
if ((mid - range[index - 1][0]) + 1 == indexK) {
return mid;
}
else if ((mid - range[index - 1][0]) + 1 > indexK)
end = mid - 1;
else
start = mid + 1;
}
return -1;
}
int main(){
int L[] = { 1, 5 };
int R[] = { 3, 8 };
int range[][2] = {{1, 3}, {5, 8}};
int n = sizeof(L) / sizeof(int);
int k = 4;
cout<<k<<"-th element of the series generated by ranges is "<<
findKthSmallestEleSeries(n, k, range);
return 0;
} আউটপুট
4-th element of the series generated by ranges is 5
