এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে। এবং Q প্রশ্ন, প্রতিটি দুটি উপাদান l এবং r নিয়ে গঠিত। আমাদের কাজ হল C++ এ একটি সাব্যারেতে স্বতন্ত্র উপাদানের সংখ্যার জন্য কোয়েরি সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা − এখানে প্রতিটি কোয়েরির জন্য, আমাদেরকে arr[l] থেকে শুরু করে arr[r] পর্যন্ত মোট স্বতন্ত্র পূর্ণসংখ্যার সংখ্যা খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
{{1, 4}, {0, 6}} আউটপুট
3 4
ব্যাখ্যা
কোয়েরির জন্য 1:l =1 এবং r =4, সাবয়ারে[1...4] ={6, 1, 6, 5}, স্বতন্ত্র উপাদানের =3।
কোয়েরির জন্য − l =0 এবং r =6, subarray[0...6] ={5, 6, 1, 6, 5, 2, 1}, স্বতন্ত্র উপাদান =4।
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমরা সেট ডেটা স্ট্রাকচার ব্যবহার করব, যার দৈর্ঘ্য কোয়েরিতে প্রদত্ত রেঞ্জের জন্য অ্যারের স্বতন্ত্র উপাদানগুলির গণনা দেবে। প্রতিটি কোয়েরির জন্য, আমরা সেটের অ্যারেতে রেঞ্জের সমস্ত উপাদান সন্নিবেশ করব। সাবয়ারের সমস্ত সদৃশ উপাদানগুলি বাতিল করা হবে এবং শুধুমাত্র স্বতন্ত্র উপাদানগুলি সংরক্ষণ করা হবে, তাই সেটের আকার স্বতন্ত্র উপাদানগুলির সংখ্যা দেবে৷
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int solveQuery(int arr[], int l, int r) {
set<int> distElements;
for (int i = (r); i >= (l); i--)
distElements.insert(arr[i]);
return distElements.size();
}
int main() {
int arr[] = {5, 6, 1, 6, 5, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
int Q = 2;
int query[Q][2] = {{1, 4}, {0,6}};
for(int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": The number of distinct elements in subarray is "<<solveQuery(arr, query[i][0], query[i][1])<<"\n";
return 0;
} আউটপুট
For Query 1: The number of distinct elements in subarray is 3 For Query 2: The number of distinct elements in subarray is 4
