शून्य बेरीजसह सर्व तिप्पट शोधा


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन जीई हेल्थकेअर Google वाढ
अरे हॅश शोधत आहे वर्गीकरण

"शून्य बेरीजसह सर्व तिप्पट शोधा" या समस्येमध्ये असे म्हटले आहे की आपणास सकारात्मक आणि नकारात्मक दोन्ही क्रमांक असलेले अ‍ॅरे देण्यात आले आहेत. प्रॉब्लेम स्टेटमेंटमध्ये ० च्या बरोबरीने त्रिपटी शोधण्यास सांगते.

शून्य बेरीजसह सर्व तिप्पट शोधा

उदाहरण

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

स्पष्टीकरण

हे तिप्पट आहेत ज्यांची बेरीज 0 आहे.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

स्पष्टीकरण

हे तिप्पट आहेत ज्यांची संख्या बेरीज 0 ⇒ -5 + 2 + 3 = 0 आहे

अल्गोरिदम

  1. क्रमवारी लावा दिलेली अ‍ॅरे
  2. सेट करा बुलियन चल isFound खोटे.
  3. मी = 0 ते i पर्यंत वळविणे
    1. सेट करा त्याचे लाकूड = i + 1, सेकंद = एन -1 आणि आणखी एक व्हेरिएबल x वर्तमान अ‍ॅरे घटकात.
    2. त्याचे लाकूड असताना
      1. घटकांपैकी तीन एकत्र मिळून 0 ची बेरीज तपासा.
        1. सत्य असल्यास, सर्व तीन क्रमांक प्रिंट करा आणि सेटफोन्ड टू ट्रू सेट करा.
      2. तीन घटकांची बेरीज (वर्तमान अ‍ॅरे घटक) 0 पेक्षा कमी आहे का ते तपासा.
        1. खरे असल्यास, त्याचे लाकूडचे मूल्य 1 ने वाढवा.
      3. तीन घटकांची बेरीज 0 पेक्षा जास्त असल्यास अन्यथा तपासा.
          1. सत्य असल्यास, से चे मूल्य १ ने कमी करा.
  4. आयएसफाउंड असत्य आहे की नाही ते तपासा, याचा अर्थ असा नाही की तिप्पटुळे तयार केली जाऊ शकत नाहीत.

स्पष्टीकरण

आम्हाला अ‍ॅरे दिली जाते. मग आपल्याला अ‍ॅरेमध्ये दिलेल्या संख्येसह तयार होणारे तिप्पट निश्चित करण्यास सांगितले जाते ज्यांची बेरीज 0 आहे. आम्ही नेस्टेड लूप वापरणार आहोत. हे अल्गोरिदम स्थिर जागेत कार्य करू शकते. प्रथम आपण अ‍ॅरे सॉर्ट करणार आहोत. अशा प्रकारे आपण दोन-सूचक तंत्र वापरू शकतो. आपण एक बुलियन व्हेरिएबल घोषित करू आणि प्रथम त्याचे मूल्य चुकीचे वर सेट करू. हे फक्त हे सुनिश्चित करण्यासाठी आहे की आम्हाला 0 असे मूल्य असलेले घटक असे कोणतेही त्रिगुण सापडले नाहीत isFound अजूनही खोटे असल्याचे बाकी आहे. जेव्हा जेव्हा आम्हाला एखादी ट्रिपलेट मिळेल तेव्हा आम्ही ते सत्य वर अद्यतनित करू. यासह, आम्ही असा निष्कर्ष काढू शकतो की कोणतेही त्रिपुरा सापडत नाही.

आपण नेस्ट केलेल्या लूपमध्ये प्रथम अ‍ॅरे सॉर्ट करू. नंतर आपण अ‍ॅरेस एन -1 पर्यंत ट्रॅव्हस करू. आम्ही प्रारंभ मूल्य i + 1 म्हणून सेट करू, अंतिम मूल्य एन -1 आणि बाह्य लूपमध्ये सध्याच्या मूल्याचे x सेट करू. आतील लूपमध्ये आपण अ‍ॅरेची व्हॅल्यूज मागे टाकू आणि तिन्ही घटकांची (x + एरर [फर] + अरर [से]] ची बेरीज 0 किंवा नाही की नाही ते तपासू. जर ते 0 असल्याचे आढळले तर याचा अर्थ असा की आम्हाला पहिली जोडी सापडली आणि अ‍ॅरेची सर्व वर्तमान व्हॅल्यूज प्रिंट केली आणि ही फाऊंड व्हॅल्यू सेट केली.

हे सूचित करते की आम्हाला एक जोड सापडली आहे. जर ट्रिपलेटची बेरीज ० इतकी नसेल तर आम्ही तपासतो की तीन वर्तमान घटकांची बेरीज ० पेक्षा कमी आहे का. जर बेरीज ० पेक्षा कमी असेल. तर आम्ही वाढवण्याचा अर्थ म्हणजे आपली प्रारंभिक मूल्य वाढविली आहे. अट समाधानी नसल्यास. बेरीज 0 पेक्षा जास्त आहे की नाही हे आम्ही तपासून बघतो तर घट से.

अशाप्रकारे, आम्ही 0 पर्यंत बेरीज होणारी सर्व संभाव्य तिप्पटे शोधत आहोत.

शून्य बेरीजसह सर्व तिप्पट्स शोधण्यासाठी सी ++ कोड

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

शून्य बेरीजसह सर्व तिप्पट्स शोधण्यासाठी जावा कोड

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन2) जेथे “एन”  अ‍ॅरे मधील घटकांची संख्या. आम्ही ओ (एन) वेळेसाठी योगदान देणारी दोन पॉईंटर तंत्र वापरत आहोत. परंतु तंत्र स्वतः ओ (एन) वेळेसाठी वापरले जाते. हे ओ (एन ^ 2) वेळेत अल्गोरिदम चालविते.

स्पेस कॉम्प्लेक्सिटी

ओ (1) अतिरिक्त जागेची आवश्यकता नसल्यामुळे.