C++-এ সর্বোচ্চ স্বতন্ত্র এলিমেন্ট বিশিষ্ট সাবসিকোয়েন্স সংখ্যা গণনা

আমাদের একটি ইন্টিজার অ্যারে দেওয়া আছে। লক্ষ্য হল সর্বোচ্চ সংখ্যক স্বতন্ত্র (distinct) এলিমেন্ট থাকা সাবসিকোয়েন্সের সংখ্যা বের করা।

উদাহরণ

ইনপুট: arr[] = {1,3,5,4,2,3,1}

আউটপুট: ৪

ব্যাখ্যা: সর্বোচ্চ ৫টি স্বতন্ত্র এলিমেন্ট: 1,2,3,4,5। সাবসিকোয়েন্স: [1,3,5,4,2], [3,5,4,2,1], [5,4,2,3,1], [1,5,4,2,3]।

ইনপুট: arr[] = {5,4,2,1,3}

আউটপুট: ১

ব্যাখ্যা: সব এলিমেন্ট স্বতন্ত্র, তাই শুধু অ্যারেটিই একমাত্র সাবসিকোয়েন্স।

অ্যালগরিদম

যদি সব এলিমেন্ট স্বতন্ত্র হয়, সাবসিকোয়েন্স = ১। যদি ডুপ্লিকেট থাকে, প্রতিটি ডুপ্লিকেট এলিমেন্টের ফ্রিকোয়েন্সি f হলে সেটি f ভিন্ন সাবসিকোয়েন্সে অবদান রাখে। তাই সব স্বতন্ত্র এলিমেন্টের ফ্রিকোয়েন্সি গুণফলই উত্তর।

1. অ্যারে এবং আকার ইনপুট নিন।
2. unordered_map দিয়ে ফ্রিকোয়েন্সি গণনা করুন।
3. count = 1 দিয়ে শুরু করুন।
4. প্রতিটি ফ্রিকোয়েন্সি f için count *= f।
5. count ফেরত দিন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

int Max_distinct_subseq(int arr[], int size) {
    int count = 1;
    unordered_map<int, int> hash;
    for (int i = 0; i < size; i++) {
        hash[arr[i]]++;
    }
    for (auto it : hash) {
        count *= it.second;
    }
    return count;
}

int main() {
    int arr[] = {3, 7, 3, 3, 1, 5, 6, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subsequences having maximum distinct elements are: " 
         << Max_distinct_subseq(arr, size);
    return 0;
}

আউটপুট

Count of subsequences having maximum distinct elements are: 3