इस लेख में, हम चौगुनी की संख्या को खोजने के लिए हर संभव दृष्टिकोण का वर्णन करेंगे जिसमें पहले 3 शब्द एपी में हैं, और अंतिम 3 जीपी में हैं। सबसे पहले, हम अंकगणितीय प्रगति (A.P.) और ज्यामितीय प्रगति (G.P.) की मूल परिभाषा की व्याख्या करेंगे।
अंकगणितीय प्रगति (ए.पी.) - यह संख्याओं का एक क्रम है जिसमें सार्व अंतर (d) समान या स्थिर होता है अर्थात दो क्रमागत संख्याओं का अंतर स्थिर होता है। उदाहरण के लिए:1,3,5,7,9 | डी =2
ज्यामितीय प्रगति (G.P.) - यह संख्याओं का एक क्रम है जिसमें उभयनिष्ठ अनुपात (r) समान होते हैं अर्थात हम पिछली संख्या को निश्चित संख्या से गुणा करके प्रत्येक पद को ज्ञात कर सकते हैं। उदाहरण के लिए:3, 6, 12, 24,.... | आर =2
इस समस्या में, हमें यह निर्धारित करने की आवश्यकता है कि N पूर्णांकों के एक सरणी arr[ ] से कितने अनुक्रमणिका चौगुनी (a, b, c, d) हैं। नतीजतन, एआर [ए], एआर [बी], और एआर [सी] एपी में हैं, और एआर [डी], एआर [सी] और एआर [बी] जीपी में हैं। जहां सभी चौगुनी निश्चित होनी चाहिए। तो यहाँ उदाहरण है -
Input : arr[ ] = { 9, 6, 4, 2, 1, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 3, 2, 1, 0 } and { 5, 2, 1, 0 } indexes where quadruples are { 2, 4, 6, 9 } for both positions.
Input : arr[ ] = { 2, 6, 1, 4, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 1, 3, 0, 2 } and { 1, 3, 4, 2 } indexes where quadruples are { 6, 4, 2, 1 } for both positions. समाधान खोजने के लिए दृष्टिकोण
अब, हम समाधान खोजने के लिए दो अलग-अलग तरीकों का वर्णन करेंगे -
क्रूर फ़ोर्स अप्रोच
चार नेस्टेड लूप का उपयोग करके इस समस्या को हल करने का यह एक आसान तरीका है, फिर जांचें कि पहले तीन तत्व एपी में हैं या नहीं। यदि हां, तो जांच लें कि अंतिम 3 तत्व जीपी में हैं या नहीं। यदि हाँ, तो गणना चर को 1 से बढ़ाएँ। हालाँकि, यह दृष्टिकोण समय लेने वाला है क्योंकि इसकी समय जटिलता O(n4) है ।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम पहले प्रत्येक सरणी तत्व की गिनती पाते हैं, फिर दोनों तत्वों को दूसरी और तीसरी संख्या मानते हुए और दो नेस्टेड लूप चलाते हैं, तो पहला तत्व होगा arr[b] – (arr[c] – एआर [बी]) और चौथा तत्व होगा 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]);
// Processing every elent and increasing the count
for (int a = 0; a < size; a++)
map[arr[a]]++;
int count = 0;
// Running two nested loops for second & third element
for (int b = 0; b < size; b++){
for (int c = 0; c < size; c++){
if (b == c)
continue;
// Decreasing the count
map[arr[b]]--;
map[arr[c]]--;
// Finding the first element using common difference
int first = arr[b] - (arr[c] - arr[b]);
// Finding the fourth element using GP
int fourth = (arr[c] * arr[c]) / arr[b];
if ((arr[c] * arr[c]) % arr[b] == 0){
// Increment count if not equal
if (arr[b] != arr[c])
count += map[first] * map[fourth];
else
count += map[first] * (map[fourth] - 1);
}
map[arr[b]]++;
map[arr[c]]++;
}
}
cout <<"Number of quadruples: " << count;
return 0;
} आउटपुट
Number of quadruples: 2
उपरोक्त कोड की व्याख्या
इस कोड में हम कॉम्बिनेटरिक्स का उपयोग कर रहे हैं और दूसरे और तीसरे तत्व के लिए दो नेस्टेड लूप का उपयोग कर रहे हैं और arr[a] – (arr[c] – arr[b]) के साथ पहला तत्व ढूंढ रहे हैं। और चौथा तत्व arr[c] *arr[c] / arr[b] के साथ . इसलिए A और B अनुक्रमणिका द्वारा चौगुनी संख्या दूसरे और तीसरे तत्व को स्थिर रखकर पहली संख्या *चौथी संख्या की गणना है। यहां समय की जटिलता उपरोक्त कोड में से O(n2) . है ।
निष्कर्ष
इस लेख में, हम चौगुनी संख्या ज्ञात करने की समस्या को हल करते हैं जहां पहले तीन शब्द एपी में हैं, और अंतिम तीन शब्द जीपी में हैं, और हमने ब्रूटफोर्स [ओ (एन 4)] और कुशल का उपयोग करके इसे हल करने के लिए दो तरीकों पर चर्चा की। दृष्टिकोण [ओ(एन2)]।
हमने C++ का उपयोग करके इस समस्या को हल किया है, और यह इस समस्या को विभिन्न अन्य भाषाओं जैसे java, python, C, या किसी अन्य प्रोग्रामिंग भाषा में हल कर सकता है।