টিমের সংখ্যা গণনা করা C++-এ

সমস্যা বিবরণ

n সংখ্যক সৈনিক একটি লাইনে দাঁড়ানো আছে, প্রত্যেকের অনন্য রেটিং আছে। ৩ জন সৈনিকের টিম বানাতে হবে যাতে তাদের রেটিং বা तो স্ট্রিক্টলি ক্রমবর্ধমান (rating[i] < rating[j] < rating[k]) অথবা স্ট্রিক্টলি ক্রমঅবর্ধমান (rating[i] > rating[j] > rating[k]) হয়। ইনডেক্স শর্ত: i < j < k। একই সৈনিক একাধিক টিমে থাকতে পারে। সার্বিক টিমের সংখ্যা বের করতে হবে।

উদাহরণ

রেটিং: [2,5,3,4,1]

বৈধ টিমগুলো:

• (2, 3, 4) — ইনডেক্স 0, 2, 3
• (5, 4, 1) — ইনডেক্স 1, 3, 4
• (5, 3, 1) — ইনডেক্স 1, 2, 4

মোট = ৩টি টিম।

অ্যালগরিদম (Brute Force)

সরল পদ্ধতিতে তিনটি নেস্টেড লুপ চালিয়ে সব সম্ভাব্য ট্রিপলেট চেক করা যায়।

• i = 0 to n-3
• j = i+1 to n-2
• k = j+1 to n-1
• শর্ত চেক করুন এবং কাউন্ট বাড়ান।

C++ বাস্তবায়ন (Brute Force)

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

class Solution {
public:
    int numTeams(vector<int>& v) {
        int ret = 0, n = v.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (v[i] < v[j] && v[j] < v[k]) ret++;
                    else if (v[i] > v[j] && v[j] > v[k]) ret++;
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,5,3,4,1};
    cout << ob.numTeams(v); // আউটপুট: 3
    return 0;
}

অপ্টিমাইজড পদ্ধতি (O(n²))

প্রতিটি মাঝপথি সৈনিক j এর জন্য:

• বামপাশে কতজন ছোট/বড় আছে — leftLess, leftGreater
• ডানপাশে কতজন ছোট/বড় আছে — rightLess, rightGreater
• ক্রমবর্ধমান টিম: leftLess * rightGreater
• ক্রমঅবর্ধমান টিম: leftGreater * rightLess
• সর্বমোট যোগ করুন।

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• Brute Force: সময় O(n³), স্থান O(1)
• অপ্টিমাইজড: সময় O(n²), স্থান O(1)