सभी विशिष्ट ट्रिपल जो एक दिए गए मूल्य तक योग करते हैं


कठिनाई स्तर मध्यम
में अक्सर पूछा एकोलाइट वीरांगना कट्टरपंथियों
ऐरे hashing खोजना

हमने ए सरणी पूर्णांकों और दी गई संख्या को 'योग' कहा जाता है। समस्या कथन दिए गए नंबर 'योग' में जुड़ने वाले ट्रिपल का पता लगाने के लिए कहता है।

उदाहरण

इनपुट:

arr [] = {3,5,7,5,6,1}

योग = 16

आउटपुट:

(3, 7, 6), (5, 5, 6)

स्पष्टीकरण:

ट्रिपल जो दी गई राशि के बराबर है.

इनपुट:

arr [] = {3,4,1,5,4}

योग = 20

आउटपुट:

कोई भी ट्रिपल नहीं हैं जो दिए गए नंबर के साथ बन सकते हैं

कलन विधि

  1. दिए गए सरणी को क्रमबद्ध करें।
  2. बूलियन चर सेट करें।
  3. जबकि i = 0 से i
    1. सेट करें j = i + 1, k = n-1।
    2. जबकि j <k
      1. जांच करें कि तीनों तत्व एक साथ दिए गए योग में हैं।
        1. अगर सच है, तो सभी तीन नंबर को प्रिंट करें और सेट करें।
      2. तीन तत्वों का योग योग से अधिक होने पर चेक करें।
        1. यदि सही है, तो k का मान 1 घटा दें।
      3. जांचें कि क्या तीन तत्वों (वर्तमान सरणी तत्व) का योग राशि से कम है।
        1. यदि सही है, तो 1 से j का मान बढ़ाएं।
  4. जाँच करें कि क्या फ़ाउंडाउंड गलत है या नहीं, यह निष्कर्ष निकालता है कि कोई ट्रिपल नहीं बनाया जा सकता है।

व्याख्या

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

सरणी को छाँटने के बाद, नेस्टेड लूप में शुरू करते हुए, हम सरणी को लंबाई n-1 तक ले जाएंगे। I + 1 के रूप में एक चर मान सेट करना, n-1 का एक और मूल्य। आंतरिक लूप में, हम एक सरणी के सभी मानों के माध्यम से पार करेंगे, और जांचेंगे कि क्या दी गई संख्या 'राशि' तीन वर्तमान सरणी तत्वों (गिरफ्तारी [i] + गिरफ्तार [j] + गिरफ्तार [k] के योग के बराबर है ]) बराबर है या नहीं। यदि स्थिति संतुष्ट हो जाती है, तो हम एक सरणी के सभी मौजूदा मूल्यों को प्रिंट करने जा रहे हैं और सेट सही है। सही मान के लिए, यह सुनिश्चित करता है कि हमें एक गलत मान वापस नहीं करना चाहिए।

यदि किसी सरणी के तीन वर्तमान मानों की संख्या दी गई संख्या के बराबर नहीं है, तो हम उसके लिए जाँच करेंगे कि यदि तीन वर्तमान तत्वों का योग दिए गए योग से कम है, यदि यह योग से कम है, तो हम मूल्य में वृद्धि करेंगे j का अर्थ है, हमारा बायाँ पॉइंटर जो बाईं ओर से संकेत करता है ट्रेवर्सल की वृद्धि हुई है और अगर यह शर्त भी संतुष्ट नहीं करती है कि हम जाँच करेंगे कि क्या राशि से अधिक है, यदि सही है, तो हम k का मान कम कर देंगे।

यह तब तक चलेगा जब तक कि सरणी के सभी मान ट्रेस नहीं हो जाएंगे। और हम isFound value को वापस करने जा रहे हैं, जिसे यदि हम तीनों में से किसी एक में पाया गया और हमें कोई भी नहीं मिला तो गलत पाया जा सकता है।

कार्यान्वयन

सभी अनोखे ट्रिपल के लिए C ++ प्रोग्राम जो एक दिए गए मूल्य के लिए योग करता है

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}
[3 6 7]
[5 5 6]

सभी अनूठे ट्रिपल के लिए जावा प्रोग्राम जो एक दिए गए मूल्य तक सम है

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}
[3 6 7]
[5 5 6]

सभी विशिष्ट ट्रिपल के लिए जटिलता विश्लेषण जो एक दिए गए मूल्य तक का योग करता है

समय जटिलता

पर2जहां "N" सरणी में तत्वों की संख्या है।

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

पर) जहां "N" सरणी में तत्वों की संख्या है।