C++-এ i < j শর্তে অদ্বিতীয় (arr[i], arr[j]) জোড়া সংখ্যা গণনা

আমাদের একটি ইন্টিজার অ্যারে দেওয়া আছে। লক্ষ্য হল অদ্বিতীয় জোড়া (arr[i], arr[j]) বের করা যাতে i < j।

উদাহরণ

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

আউটপুট: ৩

ব্যাখ্যা: (1,2), (1,3), (2,3)।

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

আউটপুট: ৪

ব্যাখ্যা: (4,4), (4,3), (4,2), (3,2)।

অ্যালগরিদম (দক্ষ পদ্ধতি)

প্রতিটি ইন্ডেক্স i-এর জন্য, তার পরের ইউনিক এলিমেন্টগুলো নির্ণয় করুন। উল্টা দিক থেকে ট্রাভার্স করে arr_2[i]-তে i-এর পরের ইউনিক এলিমেন্টের সংখ্যা সংরক্ষণ করুন। তারপর সামনে থেকে ট্রাভার্স করে প্রথমবার আসা এলিমেন্টের জন্য arr_2[i] যোগ করুন।

অ্যারে এবং আকার ইনপুট নিন।
arr_2[size] অ্যারে তৈরি করুন, arr_2[size-1] = 0।
দুটি সেট: check (পেছনের ইউনিক ট্র্যাক) এবং uncheck (সামনের ডুপ্লিকেট ট্র্যাক)।
উল্টা লুপ: i = size-1 থেকে 0। যদি arr[i] check-এ না থাকে, temp++ এবং arr_2[i-1] = temp।
সামনের লুপ: i = 0 থেকে size-2। যদি arr[i] uncheck-এ না থাকে, count += arr_2[i]।

C++ বাস্তবায়ন (দক্ষ)

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

int unique_pair(int arr[], int size) {
    int count = 0, temp = 0;
    vector<int> arr_2(size);
    arr_2[size-1] = 0;
    unordered_set<int> check, uncheck;
    
    for (int i = size - 1; i > 0; i--) {
        if (check.find(arr[i]) != check.end()) {
            arr_2[i-1] = temp;
        } else {
            arr_2[i-1] = ++temp;
        }
        check.insert(arr[i]);
    }
    
    for (int i = 0; i < size - 1; i++) {
        if (uncheck.find(arr[i]) != uncheck.end()) continue;
        count += arr_2[i];
        uncheck.insert(arr[i]);
    }
    return count;
}

int main() {
    int arr[] = {4, 3, 1, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of unique pairs (arr[i], arr[j]) such that i < j are: " 
         << unique_pair(arr, size);
    return 0;
}

আউটপুট

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10