একটি অ্যারেতে কতগুলো অনন্য জোড়া (unique pairs) তৈরি করা যায় তা বের করার জন্য C++-এর উপযুক্ত জ্ঞান প্রয়োজন। অনন্য জোড়ার সংখ্যা বের করার মানে হলো অ্যারেতে থেকে বने যেকোনো দুটি উপাদানের যোড়া (ordered pair), যেখানে প্রতিটি জোড়া অনন্য হবে। উদাহরণস্বরূপ −
ইনপুট: array[] = { 5, 5, 9 } আউটপুট: 4 ব্যাখ্যা: সব অনন্য জোড়া হলো (5, 5), (5, 9), (9, 5) এবং (9, 9)।
ইনপুট: array[] = { 5, 4, 3, 2, 2 } আউটপুট: 16
এই সমস্যা সমাধানের দুটি পদ্ধতি আছে −
এই পদ্ধতিতে, আমরা প্রতিটি সম্ভাব্য জোড়া ট্রাভার্স করব, সেগুলো একটি সেট (set) রাখব, এবং শেষে সেটের সাইজ দেখব। এই পদ্ধতির টাইম কমপ্লেক্সিটি O(n² log n)।
#include <bits/stdc++.h> using namespace std; int main () { int arr[] = { 5, 4, 3, 2, 2 }; int n = sizeof (arr) / sizeof (arr[0]); // জোড়া রাখার জন্য সেট ডিক্লেয়ার set < pair < int, int > > set_of_pairs; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) set_of_pairs.insert (make_pair (arr[i], arr[j])); int result = set_of_pairs.size(); cout << "Number of unique pairs : " << result; return 0; }
Number of unique pairs : 16
এই কোডে, প্রথমে একটি সেট ভেরিয়েবল ডিক্লেয়ার করা হয়েছে। তারপর দুটি লুপ দিয়ে প্রতিটি সম্ভাব্য জোড়া ট্রাভার্স করে সেটে ইনসার্ট করা হয়েছে। অবশেষে সেটের সাইজ বের করে ফলাফল প্রিন্ট করা হয়েছে।
অন্য একটি পদ্ধতি হলো প্রথমে অ্যারেতে কতগুলো অনন্য উপাদান আছে তা বের করা। যেহেতু প্রতিটি অনন্য উপাদান অন্য যেকোনো অনন্য উপাদানের সাথে (নিজস্ব সহ) জোড়া বানাতে পারে, তাই অনন্য জোড়ার মোট সংখ্যা = (অনন্য উপাদানের সংখ্যা)²। এই পদ্ধতির টাইম কমপ্লেক্সিটি O(n)।
#include <bits/stdc++.h> using namespace std; int main () { int arr[] = { 5, 4, 3, 2, 2 }; int n = sizeof (arr) / sizeof (arr[0]); // অনন্য উপাদান রাখার জন্য আনঅর্ডার্ড সেট unordered_set < int > set_of_elements; // উপাদানগুলো সেটে ইনসার্ট for (int i = 0; i < n; i++) set_of_elements.insert (arr[i]); int size = set_of_elements.size (); // অনন্য জোড়ার সংখ্যা = size * size int result = size * size; cout << "Number of unique pairs in an array: " << result; return 0; }
Number of unique pairs : 16
এই কোডে, একটি সেট ডিক্লেয়ার করে অ্যারেতে প্রতিটি উপাদান ইনসার্ট করা হয়েছে। তারপর সেটের সাইজ বের করে n² সূত্র দিয়ে ফলাফল প্রিন্ট করা হয়েছে।
এই আর্টিকেলে আমরা অ্যারেতে অনন্য জোড়ার সংখ্যা বের করার সমস্যা সমাধান করেছি দুটি পদ্ধতিতে: সহজ পদ্ধতি (O(n² log n)) এবং দক্ষ পদ্ধতি (O(n))। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটি সহায়ক পাবেন।
