సున్నా మొత్తంతో అన్ని ముగ్గులను కనుగొనండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ GE హెల్త్ గూగుల్ హైక్
అర్రే హాష్ శోధించండి సార్టింగ్

“సున్నా మొత్తంతో అన్ని ముగ్గురిని కనుగొనండి” సమస్య మీకు సానుకూల మరియు ప్రతికూల సంఖ్యను కలిగి ఉన్న శ్రేణిని ఇస్తుందని పేర్కొంది. సమస్య స్టేట్మెంట్ 0 కి సమానమైన మొత్తంతో త్రిపాదిని కనుగొనమని అడుగుతుంది.

సున్నా మొత్తంతో అన్ని ముగ్గులను కనుగొనండి

ఉదాహరణ

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. I = 0 నుండి i వరకు లూప్ అవుతోంది
    1. సెట్ fir = i + 1, sec = n-1 మరియు మరొక వేరియబుల్ x ప్రస్తుత శ్రేణి మూలకానికి.
    2. ఫిర్ అయితే
      1. మూడు మూలకాలు కలిసి 0 మొత్తాన్ని ఏర్పరుస్తాయో లేదో తనిఖీ చేయండి.
        1. నిజమైతే, మూడు సంఖ్యలను ప్రింట్ చేసి, isFound to true అని సెట్ చేయండి.
      2. మూడు మూలకాల మొత్తం (ప్రస్తుత శ్రేణి మూలకాలు) 0 కన్నా తక్కువగా ఉందో లేదో తనిఖీ చేయండి.
        1. నిజమైతే, ఫిర్ విలువను 1 పెంచండి.
      3. మూడు మూలకాల మొత్తం 0 కన్నా ఎక్కువగా ఉంటే వేరే తనిఖీ చేయండి.
          1. నిజమైతే, సెకను విలువను 1 తగ్గించండి.
  4. IsFound తప్పుగా ఉందో లేదో తనిఖీ చేయండి, అంటే ముగ్గులు ఏర్పడలేవు.

వివరణ

మాకు శ్రేణి ఇవ్వబడింది. అప్పుడు అర్రేలో ఇచ్చిన సంఖ్యలతో ఏర్పడే త్రిపాదిలను నిర్ణయించమని అడుగుతారు, దీని మొత్తం 0. మేము ఒక సమూహ లూప్‌ను ఉపయోగించబోతున్నాము. ఈ అల్గోరిథం స్థిరమైన ప్రదేశంలో పనిచేయగలదు. మొదట, మేము శ్రేణిని క్రమబద్ధీకరించబోతున్నాము. ఈ విధంగా మనం రెండు-పాయింటర్ పద్ధతిని ఉపయోగించవచ్చు. మేము ఒక బూలియన్ వేరియబుల్ ను డిక్లేర్ చేస్తాము మరియు దాని విలువను మొదట తప్పుగా సెట్ చేస్తాము. మూలకాల మొత్తం 0, విలువ కలిగిన మూడింటిని మనం కనుగొనలేదా అని నిర్ధారించడానికి ఇది isFound అబద్ధం. అప్పుడు మేము ముగ్గురిని కనుగొన్నప్పుడల్లా దానిని ఒప్పుకు అప్‌డేట్ చేయబోతున్నాం. కాబట్టి దీనితో, ముగ్గులు కనుగొనబడలేదని మేము నిర్ధారించగలము.

మేము మొదట శ్రేణిని సమూహ లూప్‌లో క్రమబద్ధీకరిస్తాము. అప్పుడు మేము శ్రేణిని n-1 వరకు ప్రయాణిస్తాము. మేము ప్రారంభ విలువను i + 1 గా, చివరి విలువను n-1 గా మరియు x బాహ్య లూప్‌లోని ప్రస్తుత విలువకు సెట్ చేస్తాము. లోపలి లూప్‌లో మనం శ్రేణి యొక్క విలువలను దాటుతాము మరియు మూడు మూలకాల మొత్తం (x + arr [fir] + arr [sec]) 0 కి సమానం కాదా అని తనిఖీ చేస్తాము. ఇది 0 అని తేలితే, మేము మొదటి జతను కనుగొన్నాము మరియు శ్రేణి యొక్క అన్ని ప్రస్తుత విలువలను ముద్రించాము మరియు isFound విలువను ఒప్పుకు సెట్ చేయండి.

ఇది మేము జతలలో ఒకదాన్ని కనుగొన్నట్లు సూచిస్తుంది. త్రిపాది మొత్తం 0 కి సమానం కాకపోతే, మూడు ప్రస్తుత మూలకాల మొత్తం 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) (ఇక్కడ  “N”  శ్రేణిలోని మూలకాల సంఖ్య. మేము O (n) సమయానికి దోహదపడే రెండు పాయింటర్ టెక్నిక్‌ని ఉపయోగిస్తున్నాము కాబట్టి. కానీ సాంకేతికత O (n) సమయానికి ఉపయోగించబడుతుంది. ఈ విధంగా అల్గోరిథం O (n ^ 2) సమయంలో నడుస్తుంది.

అంతరిక్ష సంక్లిష్టత

O (1) అదనపు స్థలం అవసరం లేదు.