इस लेख में, हम उन क्वाड्रपल्स की संख्या ज्ञात करने के लिए हर संभव दृष्टिकोण का वर्णन करेंगे जिनमें पहले 3 पद A.P. में हैं, और अंतिम 3 G.P. में हैं। पहले, हम अंकगणितीय प्रगति (A.P.) और ज्यामितीय प्रगति (G.P.) की बुनियादी परिभाषा समझाएंगे।
अंकगणितीय प्रगति (A.P.) - यह संख्याओं का एक क्रम है जिसमें सामान्य अंतर (d) समान या स्थिर होता है अर्थात दो लगातार संख्याओं का अंतर स्थिर होता है। उदाहरण के लिए: 1,3,5,7,9 | d = 2
ज्यामितीय प्रगति (G.P.) - यह संख्याओं का एक क्रम है जिसमें सामान्य अनुपात (r) समान होते हैं अर्थात हम प्रत्येक पद को पिछली संख्या को एक निश्चित संख्या से गुणा करके ढूंढ सकते हैं। उदाहरण के लिए: 3, 6, 12, 24,.... | r = 2
इस समस्या में, हमें यह निर्धारित करना है कि N पूर्णांकों की एक सरणी arr[] से कितने इंडेक्स क्वाड्रपल (a, b, c, d) हैं। नतीजतन, arr[a], arr[b], और arr[c] A.P. में हैं, और arr[d], arr[c] और arr[b] G.P. में हैं जहां सभी क्वाड्रपल्स निश्चित होने चाहिए। तो यहाँ उदाहरण है:
Input : arr[ ] = { 9, 6, 4, 2, 1, 2 } Output : 2 Explanation: क्वाड्रपल्स में तत्व { 3, 2, 1, 0 } और { 5, 2, 1, 0 } इंडेक्स पर हैं जहां क्वाड्रपल्स दोनों स्थितियों के लिए { 2, 4, 6, 9 } हैं। Input : arr[ ] = { 2, 6, 1, 4, 2 } Output : 2 Explanation: क्वाड्रपल्स में तत्व { 1, 3, 0, 2 } और { 1, 3, 4, 2 } इंडेक्स पर हैं जहां क्वाड्रपल्स दोनों स्थितियों के लिए { 6, 4, 2, 1 } हैं।समाधान खोजने का दृष्टिकोण
अब, हम समाधान खोजने के लिए दो अलग-अलग दृष्टिकोणों का वर्णन करेंगे:
ब्रूट फोर्स दृष्टिकोण
यह चार नेस्टेड लूप का उपयोग करके इस समस्या को हल करने का एक सरल दृष्टिकोण है, फिर जांचें कि क्या पहले तीन तत्व A.P. में हैं। यदि हाँ, तो जांचें कि अंतिम 3 तत्व G.P. में हैं या नहीं। यदि हाँ, तो काउंट चर को 1 से बढ़ाएं। हालांकि, यह दृष्टिकोण समय लेने वाला है क्योंकि इसकी समय जटिलता O(n⁴) है।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम पहले हर सरणी तत्व की गिनती ढूंढते हैं, फिर दोनों तत्वों को दूसरा और तीसरा नंबर मानकर दो नेस्टेड लूप चलाते हैं, फिर पहला तत्व arr[b] - (arr[c] - arr[b]) होगा और चौथा तत्व arr[c] * arr[c] / arr[b] होगा।
उदाहरण
#include <bits/stdc++.h> using namespace std; int main (){ unordered_map < int, int > map; int arr[] = { 2, 6, 1, 4, 2 }; int size = sizeof (arr) / sizeof (arr[0]); // हर तत्व को प्रोसेस करना और गिनती बढ़ाना for (int a = 0; a < size; a++) map[arr[a]]++; int count = 0; // दूसरे और तीसरे तत्व के लिए दो नेस्टेड लूप चलाना for (int b = 0; b < size; b++){ for (int c = 0; c < size; c++){ if (b == c) continue; // गिनती घटाना map[arr[b]]--; map[arr[c]]--; // सामान्य अंतर का उपयोग करके पहला तत्व ढूंढना int first = arr[b] - (arr[c] - arr[b]); // GP का उपयोग करके चौथा तत्व ढूंढना int fourth = (arr[c] * arr[c]) / arr[b]; if ((arr[c] * arr[c]) % arr[b] == 0){ // यदि बराबर नहीं तो काउंट बढ़ाएं if (arr[b] != arr[c]) count += map[first] * map[fourth]; else count += map[first] * (map[fourth] - 1); } map[arr[b]]++; map[arr[c]]++; } } cout <<"क्वाड्रपल्स की संख्या: " << count; return 0; }आउटपुट
क्वाड्रपल्स की संख्या: 2
उपरोक्त कोड की व्याख्या
इस कोड में हम कॉम्बिनेटोरिक्स का उपयोग कर रहे हैं और दूसरे और तीसरे तत्व के लिए दो नेस्टेड लूप का उपयोग कर रहे हैं और पहले तत्व को arr[a] - (arr[c] - arr[b]) और चौथे तत्व को arr[c] * arr[c] / arr[b] से ढूंढ रहे हैं। इसलिए A और B इंडेक्स द्वारा क्वाड्रपल्स की संख्या पहले नंबर की गिनती * चौथे नंबर की गिनती है, दूसरे और तीसरे तत्व को स्थिर रखते हुए। यहां उपरोक्त कोड की समय जटिलता O(n²) है।
निष्कर्ष
इस लेख में, हम उन क्वाड्रपल्स की संख्या ज्ञात करने की समस्या को हल करते हैं जहां पहले तीन पद AP में हैं, और अंतिम तीन पद GP में हैं, और हमने इसे हल करने के लिए दो दृष्टिकोणों पर चर्चा की: ब्रूटफोर्स [O(n⁴)] और कुशल दृष्टिकोण [O(n²)]।
हमने इस समस्या को C++ का उपयोग करके हल किया, और यह समस्या Java, Python, C, या किसी अन्य प्रोग्रामिंग भाषा में हल की जा सकती है।
