Verilən Cəmlə Cütləri Sayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Amazon Məlumat dəsti Piyada çox yol qət eləmək
Geyim Sükut Riyaziyyat çeşidləyiciBaxılıb 135

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bir tam verilir array n ölçüsü və 'K' tam ədədi ilə cəmi 'K' -ə bərabər olan massivdə mövcud olan cütlərin sayını (unikal olmamalı) hesablamalısınız.

misal

Input:

Arr = {1, 5, 7, 1}

K = 6

Çıxış:

2

Verilən Cəm ilə Count Cütləri üçün kobud güc həlli

Əsas fikir

Verilən massivin bütün cütləri üzərində təkrarlaya bilərik, sonra cəmi K-ya bərabər olan cütləri saya bilərik.

Alqoritm

  1. Dəyişən cavabı başladın = 0.
  2. 0-dan n-1 aralığında I üçün bir döngə çalıştırın
    1. J üçün i + 1-dən n-1 aralığında bir döngə çalıştırın;
      1. Arr [i] + arr [j] k-yə bərabərdirsə, cavabı 1-ə artırın.
  3. Cavabı qaytarın.

Həyata keçirilməsi

C ++ proqramı

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]+a[j]==k){
                ans++;
            }
        }
    }
    cout<<"Number of pairs with the given sum are: "<<ans;
}
4 6
1  5  7 1
Number of pairs with the given sum are: 2

JAVA proqramı

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]+a[j]==k){
                    ans++;
                }
            }
        }
    System.out.println("Number of pairs with the given sum are: "+ans);
  }
}

6 4
2 2 3 1 1 5
Number of pairs with the given sum are: 3

Verilən Cəmlə Say Cütləri üçün Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Bütün cütlər üzərində təkrarladığımız üçün və təxminən N ^ 2 cüt olduğu üçün ümumi zaman mürəkkəbliyi O (N ^ 2) -dir.

Kosmik mürəkkəblik

Əlavə yer istifadə etmədiyimiz üçün kosmik mürəkkəblik O (1).

Verilən Cəmlə Qraf Cütlər üçün Hashing Konsepsiyası

Əsas fikir

Verilən massivdə hər rəqəmin tezliyini saxlayacaq bir hash cədvəli saxlayacağıq.

İndi sıra üzərində təkrarlayacağıq və dəyəri k-arr [i] -ə bərabər olan bütün elementləri əlavə edəcəyik.

Ancaq bir şərti yoxlamalıyıq:

Arr [i] k-arr [i] -ə bərabərdirsə, fərqli cavab tapmaq məcburiyyətində olduğumuz üçün cavabımızdan 1-i çıxardacağıq, buna görə də bir cüt üçün arr [i] -i iki dəfə götürə bilmərik, buna görə bunu çıxardacağıq cavabımızdan.

Alqoritm

  1. Hər elementin sayını massivdə saxlayacaq bir hash cədvəli düzəldin.
  2. 0-dan n-1 aralığında I üçün serialı təkrarlayın
    1. Arr [i] k-arr [i] -ə bərabərdirsə, cavaba (count_of (k-arr [i]) - 1) əlavə edin.
    2. Arr [i] k-arr [i] -ə bərabər deyilsə, cavaba (count_of (k-arr [i]) əlavə edin.
  3. Cavabı qaytarın.

misal

Massiv = {1, 2, 3, 3, 4, 1, 1} üçün yaradılan hash masası:

Verilən Cəmlə Cütləri SayınPin

Həyata keçirilməsi

C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> fre;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        fre[arr[i]]++;
    }
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == k - arr[i])
        {
            answer += (fre[arr[i]] - 1);
        }
        else
        {
            answer += (fre[k - arr[i]]);
        }
    }
    answer /= 2;
    cout << "Number of pairs with the given sum are: "<<answer << endl;
    return 0;
}
6 4
1 2 2 2 3 4
Number of pairs with the given sum are: 4

JAVA proqramı

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        HashMap<Integer, Integer> fre = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            Integer j = fre.get(arr[i]); 
            fre.put(arr[i], (j == null) ? 1 : j + 1); 
        }
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == k - arr[i])
            {
                answer += (fre.get(arr[i]) - 1);
            }
            else
            {
                Integer j = fre.get(k - arr[i]); 
                if(j!=null)
                    answer += j;
            }
        }
        answer /= 2;
    System.out.println("Number of pairs with the given sum are: "+answer);
  }
}

6 7
3 5 6 1 4 4
Number of pairs with the given sum are: 3

Verilən Cəmlə Say Cütləri üçün Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yalnız bir dəfə sıra üzərində təkrarlayırıq, beləliklə zamanın mürəkkəbliyi O (N) -dir.

Kosmik mürəkkəblik

Bir hash masası saxlayırıq, buna görə kosmik mürəkkəbliyimiz O (N) dir.

References

Crack Sistemi Dizayn Müsahibələri
Translate »