এই আর্টিকেলে, আমাদের একটি অ্যারে আছে যাতে দISTINCT উপাদান রয়েছে। আমাদের একই অ্যাবসলিউট ভ্যালু (absolute value) থাকা পজিটিভ-নেগেটিভ ভ্যালু পেয়ারগুলো প্রিন্ট করতে হবে এবং সেগুলো সর্ট করা অর্ডারে প্রিন্ট করতে হবে। উদাহরণস্বরূপ:
Input : arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88} Output : -1 1 -12 12 -56 56 Input : arr[] = {30, 40, 50, 77, -51, -50, -40} Output : -40 40 -50 50
সমাধানের পদ্ধতি
আমাদের মনে যే প্রথম পদ্ধতিটি আসে সেটি হলো ব্রুট ফোর্স পদ্ধতি, এবং আমরা আরেকটি পদ্ধতি বানাবো যেটি দক্ষ পদ্ধতি। আমরা উভয় পদ্ধতিই আলোচনা করব।
ব্রুট ফোর্স পদ্ধতি
এই পদ্ধতিতে, আমরা একটি ইনডেক্স হাতে ধরে অ্যারেটি ট্রাভার্স করব এবং একই অ্যাবসলিউট ভ্যালু কিন্তু ভিন্ন ইনডেক্স খুঁজে বের করব।
উদাহরণ
#include<bits/stdc++.h> using namespace std; int main() { int arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88 }; int n = sizeof(arr)/sizeof(int); // আমাদের অ্যারের আকার। vector<int> nums; // উপস্থিত পেয়ারগুলো। for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { if(abs(arr[j]) == abs(arr[i])) { // পেয়ার খুঁজে বের করুন। nums.push_back(abs(arr[i])); break; // পেয়ার পাওয়া গেলে ইনার লুপ ব্রেক করুন কারণ অ্যারেতে দISTINCT উপাদান রয়েছে। } } } sort(nums.begin(), nums.end()); for(auto x : nums) // পেয়ারগুলো প্রিন্ট করুন। cout << -x << " " << x << " "; }
আউটপুট
-1 1 -12 12 -56 56
এই পদ্ধতিতে, আমরা অ্যারেটি ট্রাভার্স করার জন্য দুটি লুপ ব্যবহার করি এবং অন্য উপাদানটি খুঁজে বের করি। এখন যদি আমরা অন্য উপাদানটি পাই, তবে কোড দ্রুত চালানোর জন্য ইনার লুপ থেকে ব্রেক আউট করি। যেহেতু আমরা দুটি for-লুপ ব্যবহার করছি, আমাদের ওভারঅল টাইম কমপ্লেক্সিটি O(N*N)। N হল দেওয়া অ্যারের আকার যা নিম্ন কনস্ট্রেইন্টের জন্য ভালো কিন্তু উচ্চ কনস্ট্রেইন্টের জন্য ভালো নয়, তাই আমরা অন্য পদ্ধতি আলোচনা করব।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা একটি হ্যাশম্যাপ (hashmap) ব্যবহার করব যা আমাদের টাইম কমপ্লেক্সিটি যথার্থভাবে কমাতে সাহায্য করবে।
উদাহরণ
#include<bits/stdc++.h> using namespace std; int main() { int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 }; int n = sizeof(arr)/sizeof(int); // আমাদের অ্যারের আকার। map<int, int> found; // পাওয়া সংখ্যাগুলোর কাউন্ট সংরক্ষণ করবে। vector<int> nums; // উপস্থিত পেয়ারগুলো। for(int i = 0; i < n; i++) found[abs(arr[i])]++; // abs(arr[i])-এর ফ্রিকোয়েন্সি বাড়ান। for(auto x : found) { // ম্যাপ ট্রাভার্স করুন। if(x.second == 2) // যদি যেকোনো সংখ্যার ফ্রিকোয়েন্সি দুটি হয় তবে nums-এ পুশ করুন। nums.push_back(x.first); } for(auto x : nums) // পেয়ারগুলো প্রিন্ট করুন। cout << -x << " " << x << " "; }
আউটপুট
-1 1 -4 4 -8 8 -9 9
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা একটি হ্যাশম্যাপ ব্যবহার করি সংখ্যার ফ্রিকোয়েন্সি সংরক্ষণ করার জন্য। আমরা অ্যারেটি ট্রাভার্স করার সময়, বর্তমান উপাদানের অ্যাবসলিউট ভ্যালুর ফ্রিকোয়েন্সি আপডেট করি। এখন যেহেতু আপনি জানেন যে সব পেয়ারের ভ্যালু ২ হবে, তাই আমরা ম্যাপ ট্রাভার্স করি।
যদি যেকোনো সংখ্যার ফ্রিকোয়েন্সি ২ হয়, তবে আমরা সেটিকে nums-এ সংরক্ষণ করি, এবং চূড়ান্তে আমরা মানগুলো সর্ট করা অর্ডারে প্রিন্ট করি। (যেহেতু ম্যাপে সংখ্যাগুলো সর্ট করা অবস্থায় থাকে, তাই আমাদের nums ভেক্টর সর্ট করার দরকার নেই)।
উপসংহার
এই আর্টিকেলে, আমরা হ্যাশিং টেকনিক ব্যবহার করে একটি অ্যারেতে পজিটিভ-নেগেটিভ ভ্যালু পেয়ার খুঁজে বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ ও দক্ষ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
