স্বতন্ত্র উপাদান সমন্বিত সাব-অ্যারে থেকে জোড়া গঠনের গণনা (C++ প্রোগ্রাম)

আমাদের একটি অ্যারে arr[] দেওয়া আছে যেতে পূর্ণসংখ্যা উপাদান রয়েছে। লক্ষ্য হল arr[]-এর সাব-অ্যারে গুলোর উপাদান দিয়ে জোড়া গঠনের গণনা করা যেন প্রতিটি সাবঅ্যারেতে শুধু স্বতন্ত্র (distinct) উপাদান থাকে। যদি অ্যারেটি [1,2,2,3,3] হয়, তবে স্বতন্ত্র উপাদান সমন্বিত সাবঅ্যারেগুলো হবে [1,2] এবং [2,3]। এবং জোড়া হবে (1,2) এবং (2,3) অর্থাৎ জোড়ার গণনা ২।

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

আউটপুট: স্বতন্ত্র উপাদান সমন্বিত সাব-অ্যারে থেকে জোড়া গঠনের গণনা: 6

ব্যাখ্যা: স্বতন্ত্র উপাদান সমন্বিত সাবঅ্যারে: [1,2,5,3], সম্ভাব্য জোড়া (1,2), (1,3), (1,5), (2,5), (2,3), (5,3)। মোট ৬ জোড়া।

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

আউটপুট: স্বতন্ত্র উপাদান সমন্বিত সাব-অ্যারে থেকে জোড়া গঠনের গণনা: 5

ব্যাখ্যা: স্বতন্ত্র উপাদান সমন্বিত সাবঅ্যারেগুলো:

[1,2] - জোড়া: (1,2)
[2,1] - জোড়া: (2,1)
[1,2,3] - জোড়া: (1,2), (2,3), (1,3)
মোট জোড়া: 5

• ইনপুট হিসেবে পূর্ণসংখ্যা অ্যারে নিন।
• distinct_pairs(int arr[], int size) ফাংশন অ্যারে নেয় এবং স্বতন্ত্র উপাদান সমন্বিত সাব-অ্যারে থেকে জোড়া গঠনের গণনা ফেরত দেয়।
• আরম্ভিক গণনা ০ নিন। start=end=0 ভেরিয়েবল নিন।
• check(size, false) নামে একটি ভেক্টর নিন উইন্ডোর উপাদান চিহ্নিত করার জন্য।
• WHILE লুপ শুরু করুন start size-এর চেয়ে ছোট रहने পর্যন্ত।
• লুপের ভিতরে আরেকটি WHILE লুপ শুরু করুন start size-এর চেয়ে ছোট रहने পর্যন্ত AND check[arr[start]] = 0 পর্যন্ত। count কে start - end হিসেবে সেট করুন এবং check[arr[start]] কে true সেট করুন এবং start কে ১ বাড়ান।
• WHILE লুপ শুরু করুন end start-এর চেয়ে ছোট रहने পর্যন্ত AND start size-এর সমান নয় AND check[arr[start]] = true পর্যন্ত। check[arr[end]] = false সেট করুন এবং end কে ১ বাড়ান।
• count ফেরত দিন।
• ফলাফল প্রিন্ট করুন।

#include 
using namespace std;

int distinct_pairs(int arr[], int size) {
    int count = 0;
    int start = 0;
    int end = 0;
    vector check(size, false);
    while (start < size) {
        while (start < size && !check[arr[start]]) {
            count += (start - end);
            check[arr[start]] = true;
            start++;
        }
        while (end < start && (start != size && check[arr[start]])) {
            check[arr[end]] = false;
            end++;
        }
    }
    return count;
}

int main() {
    int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs formed by distinct element sub-arrays are: " << distinct_pairs(arr, size);
    return 0;
}

Count of pairs formed by distinct element sub-arrays are: 17