এই আর্টিকেলে, আমরা একটি ইউনিক সংখ্যার অ্যারেতে ইউনিক ট্রিপলেট (x, y, z) এর সংখ্যা কাউন্ট করার কথা আলোচনা করব যাদের XOR 0। ট্রিপলেটগুলো ইউনিক হতে হবে অর্থাৎ তিনটি উপাদানই ইউনিক হবে এবং আমরা ট্রিপলেটের সব কোম্বিনেশন কাউন্ট করব। উদাহরণস্বরূপ:
Input : arr[ ] = { 5, 6, 7, 1, 3 } Output : 2 Explanation : ট্রিপলেটগুলো { 5, 6, 3 } এবং { 6, 7, 1 } যাদের XOR শূন্য। Input : arr[ ] = { 3, 6, 8, 1, 5, 4 , 12} Output : 3 Explanation : ট্রিপলেটগুলো { 3, 6, 5 }, { 1, 5, 4 } এবং { 4, 8, 12 } যাদের XOR শূন্য।
সমাধানের পদ্ধতি
আমরা জানি একই ভ্যালুর XOR সবসময় শূন্য দেয়। তাই আমরা ইউনিক ট্রিপলেট খুঁজে বের করতে, একটি অপ্টিমিস্টিক (optimistic) পদ্ধতি প্রয়োগ করা যায়: অ্যারে থেকে দুটি ভ্যালুর XOR বের করে ফলাফল সংরক্ষণ করা এবং অ্যারেতে সেই ফলাফল সমান একটি ভ্যালু সার্চ করা। এছাড়া ফলাফলের ভ্যালু পেয়ারের যেকোনো ভ্যালুর সমান না হওয়া উচিত।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main () { int arr[] = { 3, 6, 8, 1, 5, 4, 12 }; int n = sizeof (arr) / sizeof (arr[0]); int result; // পেয়ার কাউন্ট রাখতে কাউন্ট ভেরিয়েবল। int count = 0; // ইউনিক সংখ্যা সংরক্ষণের জন্য সেট তৈরি। unordered_set < int >values; // সেটে ভ্যালু ইনসার্ট করুন। for (int i = 0; i < n; i++) values.insert (arr[i]); // সব পেয়ারের জন্য ট্রাভার্স করে XOR ক্যালকুলেট করুন। for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // i, j পেয়ারের XOR বের করুন। int XR = arr[i] ^ arr[j]; // চেক করুন পেয়ারের XOR ভ্যালু অ্যারেতে আছে কিনা // এবং ভ্যালু পেয়ারে না থাকা উচিত। if (values.find (XR) != values.end () && XR != arr[i] && XR != arr[j]) count++; } } // ফলাফল সংরক্ষণ result = count / 3; cout << "Number of unique triplets : " << result; return 0; }
আউটপুট
Number of unique triplets : 3
উপরোক্ত কোডের ব্যাখ্যা
- unordered_set < int >values; তৈরি করা হয়েছে দেওয়া অ্যারের ইউনিক সংখ্যা সংরক্ষণের জন্য।
- for() লুপ ব্যবহার করে values.insert (arr[i]) দিয়ে সেটে ভ্যালু ইনসার্ট করা হয়েছে।
- দুটি নেস্টেড লুপ ব্যবহার করে সব পেয়ারের মাধ্যমে ট্রাভার্স করা হয়েছে এবং তাদের XOR ভ্যালু ক্যালকুলেট করা হয়েছে।
- তারপর, XOR ভ্যালু অ্যারেতে সার্চ করা হয়েছে এবং পেয়ারে না থাকলে কাউন্ট ইনক্রিমেন্ট করা হয়েছে।
- ফলাফল হিসেবে count / 3 সংরক্ষণ করা হয়েছে কারণ ট্রিপলেটের তিনটি কোম্বিনেশন কাউন্ট হয়েছে, আর আমাদের ইউনিক ট্রিপলেট দরকার।
উপসংহার
এই আর্টিকেলে, আমরা XOR ভ্যালু ০ থাকা ট্রিপলেটের সংখ্যা বের করার কথা আলোচনা করেছি। আমরা ইউনিক ট্রিপলেট বের করার একটি অপ্টিমিস্টিক পদ্ধতি আলোচনা করেছি। আমরা এই সমস্যা সমাধানের জন্য C++ প্রোগ্রামও আলোচনা করেছি। তবে, আমরা এই প্রোগ্রামটি Java, C, Python ইত্যাদি যেকোনো প্রোগ্রামিং ভাষায়ও লিখতে পারি। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
