এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার আকার 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
ব্যাখ্যা
কোয়েরি ১: l = 1 এবং r = 4, সাবঅ্যারে[১...৪] = {6, 1, 6, 5}, স্বতন্ত্র এলিমেন্ট = ৩।
কোয়েরি ২ − l = 0 এবং r = 6, সাবঅ্যারে[০...৬] = {5, 6, 1, 6, 5, 2, 1}, স্বতন্ত্র এলিমেন্ট = ৪।
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমরা সেট ডেটা স্ট্রাকচার ব্যবহার করব, যার দৈর্ঘ্য দেওয়া রেঞ্জের স্বতন্ত্র এলিমেন্টের কাউন্ট দেবে। প্রতিটি কোয়েরির জন্য, রেঞ্জের সব এলিমেন্ট সেটে ইনসার্ট করব। সাবঅ্যারের ডুপ্লিকেট এলিমেন্টগুলো বাদ পড়বে এবং শুধু স্বতন্ত্র এলিমেন্টগুলো থাকবে, তাই সেটের আকার স্বতন্ত্র এলিমেন্টের সংখ্যা দেবে।
সমাধানের কোড উদাহরণ,
উদাহরণ
#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
