Verilən cəmi dörd element

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Goldman Sachs google microsoft Yahoo
Geyim Sükut Hashing çeşidləyici İki işarəBaxılıb 257

Problem bəyanat

Verilən problemi cəmləyən dörd elementdə biz bir vermişik array müsbət və ya mənfi ola biləcək N elementi ehtiva edir. Cəmi verilmiş k-yə bərabər olan dörd elementin çoxluğunu tapın.

Giriş Formatı

N tam ədədi olan birinci sətir.

N elementi olan bir sıra olan ikinci sətir.

Çıxış formatı

Boşluqla ayrılmış dörd tam dəyərdən ibarət olan bir sətir. Elementin sırasını hər hansı bir şəkildə yaza bilərik.

misal

Input

6

10 20 30 40 1 2

Buraxılış

20 1 30 40

Verilən cəmi dörd element üçün alqoritm

a. İki elementi və elementlərin cəmini saxlayan bir struktur yaradın.

b. (N) (n-1) / 2 ölçülü köməkçi bir sıra yaradın, köməkçi massivdə giriş cərgəsindən bütün mümkün cütləri və bunların cəmini saxlayın.

c. Beləliklə, dörd elementin hamısını tapmaq əvəzinə. Yeni köməkçidə cəmi cəminə bərabər olan bir cüt element tapmalıyıq.

d. Cütlüyü tapmaq üçün cəmi fərqlər əsasında sıralayın.

e. İndi eyni istifadə edərək cüt tapmaq alqoritm verilmiş cəmin element cütlüyünü tapmaq.

  • Dizinin sonunda birini, başlanğıcda birini iki vəziyyətdə saxlayın.
  • Cəmi cəmi> cəmi son mövqeyə keçirsə cəmi tapmaq üçün massivdə hərəkət edin.
  • Başqa birisi, əvvəlcə hərəkət et

f. Nəhayət, cəmi given_value-a bərabər olan bütün elementləri çap edin.

Həyata keçirilməsi

Verilən cəmi dörd element üçün C ++ proqramı

#include <bits/stdc++.h> 
struct pair
{
    int first_element;
    int second_element;
    int Sum;
};
int compareSums(const void *a, const void * b)
{
    return ( (*(pair *)a).Sum - (*(pair*)b).Sum );
}
 
bool isThereCommon(struct pair a, struct pair b)
{
    if (a.first_element == b.first_element || a.first_element == b.second_element || a.second_element == b.first_element || a.second_element == b.second_element)
    {
        return false;
    }
    return true;
}
 
 
void FindFour(int array[], int n, int X)
{
    int i, j;
    int size = (n*(n-1))/2;
    //auxilary array to store sums of elements
    struct pair auxiliary_array[size];
    int k = 0;
    for (i = 0; i < n-1; i++)
    {
        for (j = i+1; j < n; j++)
        {
            auxiliary_array[k].Sum = array[i] + array[j];//sum of elements
            auxiliary_array[k].first_element = i;//index of first element
            auxiliary_array[k].second_element = j;//index of second element
            k++;
        }
    }
    qsort(auxiliary_array, size,sizeof(auxiliary_array[0]),compareSums);
    i = 0;
    j = size-1;
    while (i < size && j >=0 )
    {
        if ((auxiliary_array[i].Sum + auxiliary_array[j].Sum == X) && isThereCommon(auxiliary_array[i], auxiliary_array[j]))
        {
            printf ("%d %d %d %d\n", array[auxiliary_array[i].first_element],array[auxiliary_array[i].second_element],array[auxiliary_array[j].first_element],array[auxiliary_array[j].second_element]);
            return;
        }
        else if (auxiliary_array[i].Sum + auxiliary_array[j].Sum > X)
        {
            j--;
        }
        else
        {
            i++;
        }
    }
}
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
       cin>>a[i];
    }   
    int size = sizeof(a)/sizeof(a[0]);
    int Sum = 91;
    FindFour(a,size,Sum);
    return 0;
}

Verilən cəmi dörd element üçün Java proqramı

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
class sum
{
    static class pair {
        int first, second;
        public pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
    public static void findFourElements(int arr[], int n, int X)
    {
        HashMap<Integer, pair> mp = new HashMap<Integer, pair>();
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                mp.put(arr[i] + arr[j], new pair(i, j));
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = arr[i] + arr[j];
                if (mp.containsKey(X - sum)) {
                    pair p = mp.get(X - sum);
                    if (p.first != i && p.first != j
                        && p.second != i && p.second != j) {
                        System.out.println(
                            arr[i] + " " + arr[j] + " "
                            + arr[p.first] + " "
                            + arr[p.second]);
                        return;
                    }
                }
            }
        }
        System.out.println("No Solution");
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int sum ;
        sum = sr.nextInt();
        findFourElements(arr,n, sum);
    } 
}
6
10 20 30 40 1 2
91
20 30 40 1

Verilən Cəmi Dörd Element üçün Mürəkkəblik Analizi

Zaman mürəkkəbliyi

O (n * n * logn) çünki ölçüsü (n * (n-1)) / 2 olan köməkçi massivi sıralayırıq. Və bu sıra üçün çeşidləmə n * n * log (n) vaxt aparır.

Kosmik Mürəkkəblik

O (n * n) çünki bütün cütlərin cəmini saxlamaq üçün köməkçi yer yaradırıq. Burada cütlərin ümumi sayı (n * (n-1)) / 2-dir.

References

Translate »