ఇచ్చిన విలువకు సమానమైన అన్ని ప్రత్యేకమైన ముగ్గులు


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

మేము ఒక ఇచ్చాము అమరిక పూర్ణాంకాలు మరియు ఇచ్చిన మొత్తం 'మొత్తం'. ఇచ్చిన స్టేట్మెంట్ 'సమ్' వరకు జోడించే త్రిపాదిని తెలుసుకోవడానికి సమస్య స్టేట్మెంట్ అడుగుతుంది.

ఉదాహరణ

ఇన్పుట్:

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

మొత్తం = 16

అవుట్పుట్:

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

వివరణ:

ఇచ్చిన మొత్తానికి సమానమైన త్రిపాది.

ఇన్పుట్:

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

మొత్తం = 20

అవుట్పుట్:

ఇచ్చిన సంఖ్యతో ముగ్గులు ఏర్పడవు

అల్గారిథం

  1. ఇచ్చిన శ్రేణిని క్రమబద్ధీకరించండి.
  2. బూలియన్ వేరియబుల్ isFound ను తప్పుడుకి సెట్ చేయండి.
  3. నేను = 0 నుండి i వరకు
    1. J = i + 1, k = n-1 సెట్ చేయండి.
    2. J <k అయితే
      1. మూడు మూలకాలు కలిసి ఇచ్చిన మొత్తానికి జోడించాయో లేదో తనిఖీ చేయండి.
        1. నిజమైతే, మూడు సంఖ్యలను ప్రింట్ చేసి, isFound to true అని సెట్ చేయండి.
      2. మూడు మూలకాల మొత్తం మొత్తం కంటే ఎక్కువగా ఉందో లేదో తనిఖీ చేయండి.
        1. నిజమైతే, k యొక్క విలువను 1 తగ్గించండి.
      3. మూడు మూలకాల మొత్తం (ప్రస్తుత శ్రేణి మూలకాలు) మొత్తం కంటే తక్కువగా ఉందో లేదో తనిఖీ చేయండి.
        1. నిజమైతే, j విలువను 1 పెంచండి.
  4. IsFound తప్పుగా ఉందో లేదో తనిఖీ చేయండి, అది ముగ్గులు ఏర్పడదని తేల్చింది.

వివరణ

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

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

శ్రేణి యొక్క మూడు ప్రస్తుత విలువల మొత్తం ఇచ్చిన సంఖ్యకు సమానం కాకపోతే, మూడు ప్రస్తుత మూలకాల మొత్తం ఇచ్చిన మొత్తం కంటే తక్కువగా ఉంటే, అది మొత్తం కంటే తక్కువగా ఉంటే, మేము విలువను పెంచుతాము j, అంటే ఎడమ నుండి సూచించే మా ఎడమ పాయింటర్ ట్రావెర్సల్ పెరుగుదల మరియు ఈ షరతు కూడా సంతృప్తి చెందకపోతే మొత్తం మొత్తం కంటే పెద్దదా అని మేము తనిఖీ చేస్తాము, నిజమైతే, అప్పుడు మేము k యొక్క విలువను తగ్గిస్తాము.

శ్రేణి యొక్క అన్ని విలువలు ప్రయాణించే వరకు ఇది కొనసాగుతుంది. మరియు మేము isFound విలువను తిరిగి ఇవ్వబోతున్నాము, ఇది మనకు ముగ్గులు ఏవైనా దొరికితే నిజమని మరియు మనకు ఏదీ దొరకకపోతే తప్పు అని తిరిగి ఇవ్వవచ్చు.

అమలు

ఇచ్చిన విలువకు సమానమైన అన్ని ప్రత్యేకమైన ముగ్గుల కోసం 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” శ్రేణిలోని మూలకాల సంఖ్య.