এই সমস্যায়, আমাদেরকে n পূর্ণসংখ্যার মানের একটি অ্যারে দেওয়া হয়েছে। এবং Q প্রশ্ন প্রতিটি একটি পূর্ণসংখ্যা k আছে. আমাদের কাজ হল প্রত্যয়ের মধ্যে স্বতন্ত্র পূর্ণসংখ্যার সংখ্যার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা − আমাদের প্রত্যয়ের মধ্যে স্বতন্ত্র পূর্ণসংখ্যার জন্য প্রশ্নের সমাধান করতে হবে। প্রতিটি প্রশ্নের জন্য আমাদের k থেকে n পর্যন্ত অনন্য উপাদানের সংখ্যা খুঁজে বের করতে হবে অর্থাৎ arr[k] থেকে arr[n] পর্যন্ত অনন্য উপাদান গণনা করতে হবে।
গৃহীত অ্যারে 1 সূচীকৃত।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[ ] = {5, 1, 2, 1, 6 , 5}, n = 6, Q = 3, query = {1, 3, 4} আউটপুট
4 4 3
ব্যাখ্যা
For Query 1: k = 1, N = 6, Count of elements from arr[1] to arr[6]. Count = 4. For Query 2: k = 3, N = 6, Count of elements from arr[3] to arr[6]. Count = 4 For Query 3: k = 4, N = 6, Count of elements from arr[4] to arr[6]. Count = 3
সমাধান পদ্ধতি
সূচক k থেকে শুরু করে n পর্যন্ত প্রতিটি প্রশ্নের সমাধান করার জন্য সমস্যার একটি সহজ সমাধান। এবং অ্যারের সমস্ত অনন্য উপাদান গণনা করুন এবং প্রতিটি প্রশ্নের গণনা ফেরত দিন।
কার্যকর সমাধান
সমস্যার একটি কার্যকর সমাধান হল একটি প্রাক-কম্পিউটেড ডেটা স্ট্রাকচার ব্যবহার করা যা (n-1) থেকে 0 পর্যন্ত সূচকের জন্য অনন্য গণনা সঞ্চয় করে। এটি সদৃশ উপাদানের সংযোজন বাদ দেওয়ার জন্য একটি ক্রমবিহীন সেট ব্যবহার করে করা হয়। এমনকি ঘটনা গণনার জন্য আমরা একটি সহায়ক অ্যারেও ব্যবহার করতে পারি।
আমরা শেষ থেকে শুরু করে kth উপাদান পর্যন্ত অ্যারের উপাদানগুলি যুক্ত করব এবং তারপরে ডেটা কাঠামোতে উপাদানগুলির গণনা করব (kth সূচকে অ্যারের মানের ক্ষেত্রে)।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
unordered_set<int> uniqueInts;
int distIntCount[n + 1];
for (int i = n - 1; i >= 0; i--) {
uniqueInts.insert(arr[i]);
distIntCount[i + 1] = uniqueInts.size();
}
for (int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": the number of distinct integers in Suffix is "<<distIntCount[queries[i]]<<endl;
}
int main() {
int n = 6, Q = 3;
int arr[n] = {5, 1, 2, 1, 6, 5};
int queries[Q] = {1, 3, 4};
solveQueries_DistInt(n, arr, Q, queries);
return 0;
} আউটপুট
For Query 1: the number of distinct integers in Suffix is 4 For Query 2: the number of distinct integers in Suffix is 4 For Query 3: the number of distinct integers in Suffix is 3
