এই সমস্যায়, একটি সর্টেড অ্যারে দেওয়া থাকে এবং আমাদের অ্যারיתমেটিক প্রোগ্রেশন (AP) ফর্মের ট্রিপলেট খুঁজে বের করতে হবে।
একটি অ্যারithmetic প্রোগ্রেশন হলো এমন একটি সিরিজ যেখানে কনsekutিভ টার্মের মধ্যে ডিফারেন্স একই থাকে।
উদাহরণ দিয়ে বুঝি:
ইনপুট: array = {2, 5, 7, 8, 9, 10} আউটপুট: 2 5 8 5 7 9 7 8 9 8 9 10এই সমস্যাটি সমাধান করার একটি সহজ সমাধান হবে তিনটি লুপ চালিয়ে সব ট্রিপলেট চেক করা যে সেগুলো AP-তে আছে কিনা। কিন্তু এই মেথডের টাইম কমপ্লেক্সিটি n³।
একটি আরও ভালো সমাধান হলো হ্যাশিং ব্যবহার করা। এই মেথডে, আমরা অ্যারের দ্বিতীয় এলিমেন্ট থেকে শুরু করব এবং প্রতিটি এলিমেন্টকে AP-এর মাঝপথের এলিমেন্ট মনে করব এবং চেক করব যে সেটি AP তৈরি করে কিনা।
C++ উদাহরণ
#include <iostream> using namespace std; void TripletsAP(int arr[], int n){ for (int i = 1; i < n - 1; i++){ for (int j = i - 1, k = i + 1; j >= 0 && k < n;){ if (arr[j] + arr[k] == 2 * arr[i]){ cout<<arr[j]<<"\t"<<arr[i]<<"\t"<< arr[k] << endl; k++; j--; } else if (arr[j] + arr[k] < 2 * arr[i]) k++; else j--; } } } int main(){ int arr[] = {2, 5, 7, 8, 9, 10}; int n = sizeof(arr) / sizeof(arr[0]); cout<<"The triplets that are in AP are : \n"; TripletsAP(arr, n); return 0; }আউটপুট
AP-তে থাকা ট্রিপলেটগুলো হলো:
2 5 8 5 7 9 7 8 9 8 9 10
