इस समस्या में, हमें संख्याओं की एक क्रमबद्ध सरणी दी गई है और हमें उन ट्रिपलेट को ढूंढना है जो अंकगणितीय प्रगति (AP) के रूप में हैं।
एक अंकगणितीय प्रगति संख्याओं की एक श्रृंखला है जिसमें लगातार पदों के बीच का अंतर समान होता है।
समस्या को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
इनपुट: सरणी = {2 , 5 , 7, 8 , 9 , 10} आउटपुट: 2 5 8 5 7 9 7 8 9 8 9 10 इस समस्या को हल करने का एक सरल समाधान तीन लूप चलाना और जांचना होगा कि क्या सभी ट्रिपलेट AP में हैं। लेकिन इस विधि की समय जटिलता n^3 क्रम की है।
एक बेहतर समाधान हैशिंग का उपयोग करना है। इस विधि में, हम सरणी के दूसरे तत्व से शुरू करेंगे और प्रत्येक तत्व को AP के मध्य तत्व के रूप में मानेंगे और जांचेंगे कि क्या यह AP बनाता है या नहीं।
उदाहरण
#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
