גראף פּערז מיט געגעבן סומע  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַקקאָליטע אַמאַזאָן פאַקסעט שפּאַציר
מענגע האַש מאַט סאָרטינג

געגעבן אַ ינטאַדזשער מענגע פון גרייס n און אַ גאַנץ נומער 'K', איר דאַרפֿן צו ציילן די נומער פון פּערז (ניט דאַרפֿן צו זיין יינציק) אין די מענגע וועמענס סומע איז גלייַך צו 'K'.

בייַשפּיל  

ינפּוט:

Arr = {1, 5, 7, 1}

ק = 6

אָוטפּוט:

2

ברוט קראַפט לייזונג פֿאַר גראף פּערז מיט געגעבן סאַכאַקל  

הויפּט געדאַנק

מיר קענען יבערקוקן איבער אַלע פּערז פון די געגעבן מענגע און דאַן ציילן די פּערז וועמענס סאַכאַקל איז גלייַך צו ק.

אַלגאָריטהם

  1. יניטיאַליזירן אַ בייַטעוודיק ענטפער = 0.
  2. לויפן אַ שלייף פֿאַר איך אין קייט 0 צו N-1
    1. לויפן אַ שלייף פֿאַר דזש אין קייט איך + 1 צו נ -1;
      1. אויב אַרר [i] + אַרר [j] איז גלייַך צו k, דאַן פאַרגרעסערן ענטפער מיט 1.
  3. ענטפער צוריק.

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם

#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 פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר גראף פּערז מיט געגעבן סומע

צייט קאַמפּלעקסיטי

ווי מיר יטערירן איבער אַלע פּערז און עס זענען בעערעך N ^ 2 פּערז, אַזוי די גאַנץ צייט קאַמפּלעקסיטי איז O (N ^ 2).

זע אויך
ספּעציעלע נומער

אָרט קאַמפּלעקסיטי

מיר האָבן נישט געניצט אַן עקסטרע פּלאַץ, אַזוי די פּלאַץ קאַמפּלעקסיטי איז אָ (1).

האַשינג באַגריף פֿאַר גראף פּערז מיט געגעבן סומע  

הויפּט געדאַנק

מיר וועלן האַלטן אַ האַש טיש וואָס וועט קראָם די אָפטקייַט פון יעדער נומער אין די געגעבן מענגע.

איצט מיר וועלן יבערקוקן די מענגע און לייגן אַלע די יסודות וועמענס ווערט איז גלייַך צו ק-אַרר [i].

אָבער מיר האָבן צו קאָנטראָלירן איין צושטאַנד:

אויב אַרר [i] איז גלייך ק-אַרר [i], מיר וועלן אַראָפּרעכענען 1 פון אונדזער ענטפער ווייַל מיר מוזן געפֿינען פאַרשידענע פּערז, אַזוי מיר קענען נישט נעמען אַרר [i] צוויי מאָל פֿאַר אַ פּאָר. דעריבער מיר וועלן אַראָפּרעכענען דעם פאַל פון אונדזער ענטפער.

אַלגאָריטהם

  1. מאַכן אַ האַש טיש וואָס וועט קראָם די ציילן פון יעדער עלעמענט אין די מענגע.
  2. יטעראַטע די מענגע פֿאַר איך אין קייט 0 צו נ -1
    1. אויב אַרר [i] איז גלייַך צו k-arr [i], דאַן לייג (קאַונט_אָף (ק-אַרר [איך]) - 1) צו דעם ענטפער.
    2. אויב אַרר [i] איז נישט גלייך ווי k-arr [i], לייג צו (count_of (k-arr [i]) צו דעם ענטפער.
  3. ענטפער צוריק.

בייַשפּיל

האַש טיש באשאפן פֿאַר די מענגע = {1, 2, 3, 3, 4, 1, 1} איז:

גראף פּערז מיט געגעבן סומעשפּילקע

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם

#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 פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר גראף פּערז מיט געגעבן סומע

צייט קאַמפּלעקסיטי

מיר יבערקוקן נאָר איין מאָל איבער די מענגע, אַזוי די צייט קאַמפּלעקסיטי איז אָ (ען).

זע אויך
געפֿינען אַ פּאָר מיט גרעסטע פּראָדוקט אין עריי

אָרט קאַמפּלעקסיטי

מיר האַלטן אַ האַש טיש, אַזוי אונדזער פּלאַץ קאַמפּלעקסיטי איז אָ (ען).

רעפֿערענצן