იპოვნეთ Triplet მასივში მოცემული თანხით  


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი Adobe Amazon Apple Bloomberg ByteDance Cisco ციხედ Citrix DoorDash eBay Facebook Goldman Sachs Google Hulu IBM Infosys მათემატიკის სამუშაოები microsoft Morgan Stanley Oracle PayPal Qualtrics Samsung სერვისი გაღრმავება Square Tencent Tesla Uber Visa VMware Walmart Labs Yahoo Zoho
Akamai Array CarWale Groupon ფოსტა მუშაობს პროგრამები

პრობლემის განცხადება  

მთელი რიცხვების მასივის გათვალისწინებით, იპოვნეთ სამი ელემენტის კომბინაცია მასივი რომლის ჯამი მოცემული მნიშვნელობის ტოლია X. აქ ჩვენ დავბეჭდავთ პირველ კომბინაციას, რომელსაც მივიღებთ. თუ ასეთი კომბინაცია არ არსებობს, დაბეჭდეთ -1.

მაგალითი  

შეყვანის

N = 5, X = 15

arr [] = {10, 4, 2, 3, 5}

გამოყვანის 

10, 2, 3

მიდგომა 1  

ყველა სამეულის გენერირება და ჯამის შედარება მოცემულ მნიშვნელობასთან. ქვემოთ მოცემული ალგორითმი შეიცავს სამ მარყუჟს.

ალგორითმი

  1. პირველი დაალაგეთ შეყვანის მასივი
  2. პირველი ელემენტის დაფიქსირება arr [i] - ით, სადაც i მერყეობს 0-დან N-2-მდე.
  3. პირველი ელემენტის დაფიქსირების შემდეგ დააფიქსირეთ მეორე ელემენტი arr [j] - ით, სადაც j მერყეობს i + 1 – დან N– 1 – მდე.
  4. მეორე ელემენტის დაფიქსირების შემდეგ დააფიქსირეთ მესამე ელემენტი arr [k] - ით, სადაც k მერყეობს j + 1– დან N– მდე.
  5. იპოვნეთ ჯამი, arr [i] + arr [j] + arr [k].
  6. თუ Triplet თანხა უდრის X მნიშვნელობას, დაბეჭდეთ სამი სხვა ელემენტი ბეჭდვა -1.

განხორციელება

C ++ პროგრამა მასივში სამმაგი პოვნისათვის მოცემული ჯამით

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            for(int k=j+1;k<N;k++)
            {
                if( arr[i] + arr[j] + arr[k] == X)
                {
                   cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
                   return 1;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

Java პროგრამა მასივში სამმაგის პოვნისთვის მოცემული ჯამით

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if( a[i] + a[j] + a[k] == x)
                    {
                       System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                       i=n;j=n;k=n;
                       temp=1;
                    }
                }
            }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
10 4 2 3 5
10  2  3

სირთულის ანალიზი

დროის სირთულე

O (n * n * n) სადაც n არის მასივში არსებული ელემენტების რაოდენობა. ჩვენ რონ სამს ვუყურებთ მარყუჟისთვის და ვამოწმებთ ყველა შესაძლო სამეულს.

იხილეთ ასევე
გამოიცანით სიტყვა

სივრცის სირთულე

O (1) რადგან აქ არ ვხმარობთ რაიმე დამხმარე ადგილს.

მიდგომა 2  

ალგორითმი

  1. პირველი სახის შეყვანის მასივი
  2. პირველი ელემენტის დაფიქსირება arr [i] - ით, სადაც i მერყეობს 0-დან N-2-მდე.
  3. პირველი ელემენტის დაფიქსირების შემდეგ, შემდეგი ორი ელემენტის მოსაძებნად, აიღეთ ორი მაჩვენებლის მსგავსი ცვლადები (j = i + 1, k = N-1) და გადალახეთ დალაგების მასივში ჯამის პოვნის ალგორითმი.
  4. მიუხედავად იმისა, რომ j ნაკლებია k– ზე მოცემულ ინდექსებში დაამატეთ ელემენტები, მაგ., Arr [i] + arr [j] + arr [k], თუ Triplet sum უდრის X მნიშვნელობას, სხვა ელემენტი დაბეჭდეთ თუ Triplet sum ნაკლებია მნიშვნელობა X, შემდეგ გაზრდის j მნიშვნელობას და სხვას შეამცირებს k მნიშვნელობას.

განხორციელება

C ++ პროგრამა მასივში სამმაგი პოვნისათვის მოცემული ჯამით

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N,X;//size of the array
    cin>>N>>X;
    int arr[N];
    for(int i=0;i<N;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+N); //sort the array in ascending order
    int computed_sum;//sum computed at each step
  
    for(int i = 0; i < N - 2; i++) // fix one element and search for other two elements in linear time
    {
      int j = i+1 , k = N-1; // jth index starts from the next element of selected and k always starts at the ending index
      
      while(j < k)
      {
        computed_sum = arr[i] + arr[j] + arr[k]; // add the elements at the given indices
        
        if(computed_sum == X)
          {
            cout << arr[i] <<"  "<<arr[j]<<"  "<<arr[k];
            return 1;
          }
        else if(computed_sum < X) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
          j++;
          
        else if(computed_sum > X)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
          k--;
      }
    }
  cout<<-1<<endl;
    return 0;
}

Java პროგრამა მასივში სამმაგის პოვნისთვის მოცემული ჯამით

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a); //sort the array in ascending order
        int computed_sum;//sum computed at each step
        int temp=0;
        for(int i = 0; i < n - 2; i++) // fix one element and search for other two elements in linear time
        {
          int j = i+1 , k = n-1; // jth index starts from the next element of selected and k always starts at the ending index
          while(j < k)
          {
            computed_sum = a[i] + a[j] + a[k]; // add the elements at the given indices
            if(computed_sum == x)
              {
                System.out.println(a[i]+"  "+a[j]+"  "+a[k]);
                j=k;
                temp=1;
              }
            else if(computed_sum < x) // means we need to increase some element but as i is fixed and k is already higher than i and j. We increment jth index
              j++;
            else if(computed_sum > x)//means we need to decrease some element but as i is fixed and j is already smaller than kth index element , we decrement k
              k--;
          }
        }
        if(temp==0)
        System.out.println(-1);
    }
}
5 15
1 4 2 3 5
-1

სირთულის ანალიზი

დროის სირთულე

O (n * n * n) სადაც n არის მასივში არსებული ელემენტების რაოდენობა. ჩვენ რონ სამს ვუყურებთ მარყუჟისთვის და ვამოწმებთ ყველა შესაძლო სამეულს.

იხილეთ ასევე
დაბეჭდეთ ყველა სამეული სამი დახარისხებული მასივით, რომელიც ქმნის AP- ს

სივრცის სირთულე

O (1) რადგან აქ არ ვხმარობთ რაიმე დამხმარე ადგილს.

ლიტერატურა