دی گئی رقم کے ساتھ جوڑے گنیں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے اکٹھا کرنا ایمیزون حقیقت اضافہ
لڑی ہیش ریاضی چھانٹ

ایک عدد عدد دیا صف سائز این ، اور ایک عددی 'K' کے ل، ، آپ کو صف میں موجود جوڑے کی تعداد (انوکھا ہونے کی ضرورت نہیں) گننے کی ضرورت ہے جس کا مجموعہ 'K' کے برابر ہے۔

مثال کے طور پر

ان پٹ:

ارر = {1 ، 5 ، 7 ، 1}

K 6 =

: پیداوار

2

دی گئی رقم کے ساتھ گنتی کے جوڑے کیلئے بروٹ فورس حل

مرکزی خیال

ہم دیئے گئے صف کے سارے جوڑے پر تکرار کرسکتے ہیں ، اور پھر ان جوڑوں کی گنتی کرسکتے ہیں جس کا جوڑ K کے برابر ہے۔

الگورتھم

  1. متغیر جواب = 0 شروع کریں۔
  2. I کے ل 0 1 سے n-XNUMX میں لوپ چلائیں
    1. رینج i + 1 سے n-1 میں j کے لئے ایک لوپ چلائیں۔
      1. اگر ار [[i] + ارر [ج] کے برابر ہے تو ، جواب میں 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

جاوا پروگرام

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) ہے۔

خلائی پیچیدگی

ہم نے کوئی اضافی جگہ استعمال نہیں کی ہے ، لہذا جگہ کی پیچیدگی O (1) ہے۔

دی گئی رقم کے ساتھ گنتی کے جوڑے کے لئے ہیشنگ تصور

مرکزی خیال

ہم ایک ہیش ٹیبل برقرار رکھیں گے جو دیئے گئے صف میں ہر نمبر کی تعدد کو اسٹور کرے گا۔

اب ہم صف پر اعادہ کریں گے اور ان تمام عناصر کو شامل کریں گے جن کی قیمت کے آر آر کے برابر ہے [i]۔

لیکن ہمیں ایک شرط دیکھنی ہے۔

اگر ار [[i] کے آر آر کے برابر ہے [i] ، تو ہم اپنے جواب سے 1 کو گھٹائیں گے کیونکہ ہمیں الگ جوڑ ڈھونڈنا ہے ، لہذا ہم ایک جوڑا کے لئے دو مرتبہ آر آر نہیں لے سکتے ہیں ، اسی وجہ سے ہم اسے گھٹا لیں گے۔ ہمارے جواب سے معاملہ

الگورتھم

  1. ہیش ٹیبل بنائیں جو ہر عنصر کی گنتی کو صف میں محفوظ کرے گی۔
  2. رینج 0 سے لے کر n-1 میں I کے لئے سرے کی جانچ کریں
    1. اگر ار [[i] کے ار آر کے برابر ہے [i] ، تو اس کے جواب میں (کاؤنٹی_وف (کے آر آر [i]) - 1 شامل کریں۔
    2. اگر ار [[i] کے ار آر کے برابر نہیں ہے [i] ، تو پھر جواب میں (کاؤنٹی_وف (کے آر آر [i]) شامل کریں۔
  3. جواب واپس کریں۔

مثال کے طور پر

سرنی = {1، 2، 3، 3، 4، 1، 1 XNUMX کے لئے تیار کردہ ہیش ٹیبل ہے:

دی گئی رقم کے ساتھ جوڑے گنیں

عمل

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

جاوا پروگرام

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

دی گئی رقم کے ساتھ گنتی کے جوڑے کیلئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی

ہم صرف ایک بار صف پر تکرار کرتے ہیں ، لہذا وقت کی پیچیدگی O (N) ہوتی ہے۔

خلائی پیچیدگی

ہم ہیش ٹیبل کو برقرار رکھے ہوئے ہیں ، لہذا ہماری خلائی پیچیدگی O (N) ہے۔

حوالہ جات