सॉर्ट किए गए सरणी में सभी ट्रिपल प्रिंट करें जो एपी बनाते हैं


कठिनाई स्तर मध्यम
में अक्सर पूछा एक्सेंचर एकोलाइट ताल भारत गूगल जानकारी सहज Pinterest
ऐरे हैश खोजना

समस्या "सॉर्ट किए गए एरे में सभी ट्रिपल प्रिंट करें जो एपी बनाते हैं" बताता है कि हमने एक सॉर्ट दिया है पूर्णांक सरणी। कार्य सभी संभावित ट्रिपल का पता लगाना है जो एक अंकगणितीय प्रगति बना सकता है।

सॉर्ट किए गए सरणी में सभी ट्रिपल प्रिंट करें जो एपी बनाते हैं

उदाहरण

arr[] = {1,3,5,7,8,12,15,16,20,30}
(1, 3, 5), (3, 5, 7), (1, 8, 15), (8, 12, 16), (12, 16, 20)

व्याख्या

ये सभी त्रिभुज हैं जो एक एपी बनाते हैं

arr[] = {2,4,5,6,9,14,18,24}
(2, 4, 6), (4, 5, 6), (4, 9, 14), (4, 14, 24)

व्याख्या

ये सभी त्रिभुज हैं जो एक एपी बनाते हैं

कलन विधि

  1. से पाश i = 1 से n-1(शामिल नहीं)।
  2. J का मान I से कम और k का मान i से एक अधिक सेट करें।
  3. जबकि j> = 0 && k <n.
    1. जांचें कि क्या दो वर्तमान सरणी तत्वों का योग अन्य सरणी तत्व के दोगुने के बराबर है,
      1. यदि सही है, तो वर्तमान तीन तत्वों को प्रिंट करें और क्रमशः कश्मीर और जे के मूल्य में कमी और वृद्धि करें।
    2. जांचें कि क्या दो तत्वों का योग दूसरे तत्व के दोगुने से कम है, तो, k को 1 से बढ़ाएं।
    3. जांचें कि क्या दो तत्वों का योग दूसरे तत्व के दोगुने से अधिक है, तो, j 1 से घटाएं।

व्याख्या

हमने ए छाँटे गए सरणी। हमें उन सभी ट्रिपल का पता लगाने के लिए कहा जाता है जो एक अंकगणित प्रगति का गठन कर सकते हैं। एक अंकगणितीय प्रगति को एक संख्या अनुक्रम के रूप में परिभाषित किया जा सकता है जिसमें सभी तत्व पूरे अनुक्रम के साथ उनके बीच एक विशेष दूरी के साथ लगातार आते हैं। हम ट्रिपल को एक एपी के सूत्र द्वारा पाएंगे जो बताता है कि a + c = 2b है यदि दो संख्याओं का योग तीसरी संख्या के दोगुने के बराबर है।

लूप और ए के लिए पूरे सरणी को एक के साथ पार करें घुमाव के दौरान, 'जबकि लूप' यह जांचने जा रहा है कि क्या हम तीनों में से एपी को बना सकते हैं या नहीं। हम j के मान को i के मान से कम और k के मान को i के मान से एक से अधिक पर सेट करेंगे, जब भी हम लूप के लिए पार करेंगे। यह हमारे लिए जाँच करने के लिए एक तत्व उठाएगा, इसलिए हर बार हमारे पास गिरफ्तारी [i], गिरफ्तारी [j], और गिरफ्तारी [k], i, j, और k का मान जाँचने के लिए तीन तत्व होंगे जो प्रत्येक के लिए अलग-अलग होंगे। ट्रैवर्सल चाहे लूप में हो या अंदर घुमाव के दौरान.

यदि हमने पाया कि दो तत्वों का योग तीसरे तत्व के बराबर है, तो हम उन तीन सरणी तत्वों को प्रिंट करने जा रहे हैं, वे एक एपी बना सकते हैं। हम अपने एल्गोरिथ्म के अनुसार जम्मू और कश्मीर के मूल्य को अपडेट करेंगे। अगर हमें दो तत्वों का योग तीसरे तत्व के दोगुने से कम मिला। हम k का मान बढ़ाएंगे, या यदि हमें तीसरे तत्व के दोगुने से अधिक योग मिला, तो हम j का मान घटाते हैं। यह तब तक चलेगा जब तक हम पूरे सरणी को पार नहीं कर लेते हैं और सभी संभावित तत्वों का पता लगा सकते हैं जो एपी बना सकते हैं।

कोड

C ++ कोड को सॉर्ट किए गए सरणी में सभी ट्रिपल प्रिंट करने के लिए जो एपी बनाते हैं

#include<iostream>

using namespace std;

void getTripletsWithAP(int arr[], int n)
{
  for (int i = 1; i < n - 1; i++)
  {
    int j = i - 1, k = i + 1;
        while(j >= 0 && k < n)
        {
            if (arr[j] + arr[k] == 2 * arr[i])
            {
        cout <<arr[j]<< " "<<arr[i]<<" "<<arr[k]<< endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;
            else
                j--;
        }
  }
}
int main()
{
  int arr[] = {1,3,5,7,8,12,15,16,20,30};
  int n = sizeof(arr) / sizeof(arr[0]);
  getTripletsWithAP(arr, n);
  return 0;
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

जावा कोड एपी बनाने वाले सॉर्ट किए गए सरणी में सभी ट्रिपल प्रिंट करने के लिए

class TripletAP
{
    public static void getTripletsWithAP(int arr[], int n)
    {
        for (int i = 1; i < n - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < n)
            {
                if (arr[j] + arr[k] == 2 * arr[i])
                {
                    System.out.println(arr[j] +" " +arr[i]+ " " + arr[k]);
                    k++;
                    j--;
                }
                else if (arr[j] + arr[k] < 2 * arr[i])
                    k++;
                else
                    j--;
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {1,3,5,7,8,12,15,16,20,30};
        int n = arr.length;
        getTripletsWithAP(arr, n);
    }
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

जटिलता विश्लेषण

समय जटिलता

पर2जहां "N"  सरणी में तत्वों की संख्या है। क्योंकि हमारे पास दो नेस्टेड लूप हैं जहां पहला लूप तब तक चलता है जब तक हम अंत तक नहीं पहुंच जाते हैं और फिर दूसरे नेस्टेड लूप का उपयोग एपी के तत्वों को खोजने के लिए किया जाता है।

अंतरिक्ष जटिलता

ओ (1) के रूप में कोई अतिरिक्त स्थान की आवश्यकता है।