دو غیر ترتیب شدہ اشاروں سے تمام جوڑے مل جاتے ہیں جن کا مجموعہ x ہے


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

مسئلہ یہ بیان

غیر ترتیب شدہ دو دیئے گئے صفیں، ان تمام جوڑے کو ڈھونڈو جس کی رقم x مسئلہ ہے جس میں کہا گیا ہے کہ آپ کو انٹیجرز کی دو صفیں دی گئ ہیں جو غیر ترتیب شدہ ہیں اور ایک ویلیو جس کی قیمت ہے۔ مسئلے کے بیان میں جوڑے کی کل تعداد معلوم کرنے اور ان تمام جوڑے کو پرنٹ کرنے کے لئے کہا گیا ہے جو دیئے گئے ویلیو میں جوڑے کو کہتے ہیں۔

مثال کے طور پر

arr1[] = { 3,6,1,4,8,2}

arr2[] = { 2,1,5,7,2,4}

sum = 9
(8, 1), (4, 5) (2, 7)

وضاحت: تینوں جوڑے کی ایک ایسی تعداد ہوتی ہے جس میں دئے گئے قدر 9 کے برابر رقم ہوتی ہے۔

arr1[] = { 2,5,1,7,9}

arr2[] = { 3,6,8,1,0}

sum = 7
(1, 6), (7, 0)

وضاحت: دونوں دونوں جوڑے کی ایک ایسی تعداد ہوتی ہے جس کی دی گئی قیمت 7 کے برابر رقم ہوتی ہے۔

دو غیر ترتیب شدہ صفوں میں جوڑے = x والے تمام جوڑے تلاش کرنے کے لئے الگورتھم

1. Declare a Set.
2. Insert all the values of array1 into the Set.
3. Traverse the array2.
4. Check if the difference of sum and each number of array2 is present in a set.
5. If present then prints the difference and the current array element.

وضاحت

دو غیر ترتیب شدہ صفوں کو دیئے گئے ، وہ تمام جوڑے تلاش کریں جن کا مجموعہ x ہو۔ اس کے لئے ، ہم سیٹ کو استعمال کرنے جا رہے ہیں۔ ایک سیٹ عام عناصر کو ختم کرنے کی ایک خصوصیت بھی فراہم کرتا ہے۔ ہم جو کرنے جا رہے ہیں وہ یہ ہے کہ ہم صف میں صفی کی تمام اقدار داخل کریں گے۔ یہاں ، اگر سیٹ عناصر کو ہٹاتا ہے یا نہیں کرتا ہے۔ ہمیں اس کی زیادہ پرواہ نہیں ہے کیونکہ ہمیں یہ چیک کرنے کے لئے صرف نمبر کی ضرورت ہے کہ جوڑی تشکیل پاسکتی ہے یا نہیں۔

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

دوسرے صف کے پہلے عنصر کے لئے شروع کرتے ہوئے ہم ٹراورس کرتے وقت دیئے گئے قدر اور دوسرے صف کی ہر قیمت کے فرق کی جانچ کریں گے۔ یہ بھی اسی طرح کی بات ہے کیونکہ ہم دو نمبر جوڑ سکتے ہیں جس میں a + b = c کہتے ہیں ، اور اب اگر ہمارے پاس صرف b اور c ہے تو ، ہمیں 'a' کا پتہ لگ سکتا ہے۔ ایک ہی چیز یہ ہے کہ ہمارے پاس نتیجہ خیز قیمت ہے جو ہم تلاش کرسکتے ہیں کہ جوڑی کو مکمل کرنے کے لئے کس قدر کی ضرورت ہے۔ اسی لئے ہم سرسری میں 2 کے فرق اور ارای 1 میں سے ہر ایک کی قیمت تلاش کر رہے ہیں۔ اگر ہم جوڑا تلاش کریں کہ جوڑی اور موجودہ صف عنصر کے فرق کو صرف پرنٹ کریں تو یہ مطلوبہ جوڑی ہوگی۔

دو غیر ترتیب شدہ صفوں کو دیئے گئے ، وہ تمام جوڑے تلاش کریں جن کا مجموعہ x ہو

ضابطے

سی ++ کوڈ جس میں دو جوڑے ہوئے صفوں میں جوڑ = x والے تمام جوڑے مل جاتے ہیں

#include<iostream>
#include<unordered_set>

using namespace std;

void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
{
    unordered_set<int> MAP;
    for (int i = 0; i < l1; i++)
        MAP.insert(arr1[i]);

    for (int j = 0; j < l2; j++)
        if (MAP.find(sum - arr2[j]) != MAP.end())
            cout << sum - arr2[j] << " "<< arr2[j] << endl;
}
int main()
{
    int arr1[] = { 3,6,1,4,8,2};
    int arr2[] = { 2,1,5,7,2,4};
    int sum = 9;
    int l1 = sizeof(arr1) / sizeof(int);
    int l2 = sizeof(arr2) / sizeof(int);
    getPairsofSum(arr1, arr2, l1, l2, sum);
    return 0;
}
8 1
4 5
2 7

 

جاوا کوڈ جس میں دو جوڑے ہوئے صفوں میں جوڑ = x والے تمام جوڑے مل جاتے ہیں

import java.util.HashMap;

class PairofSumUnsortedArray
{
    public static void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        for (int i = 0; i < l1; i++)
            MAP.put(arr1[i], 0);

        for (int j = 0; j < l2; j++)
            if (MAP.containsKey(sum - arr2[j]))
                System.out.println(sum - arr2[j] + " " + arr2[j]);
    }
    public static void main(String[] args)
    {
        int arr1[] = { 3,6,1,4,8,2};
        int arr2[] = { 2,1,5,7,2,4};
        int sum = 9;
        getPairsofSum(arr1, arr2, arr1.length, arr2.length, sum);
    }
}
8 1
4 5
2 7

 

پیچیدگی کا تجزیہ

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

O (زیادہ سے زیادہ (ن ، ایم)) کہاں "این" اور "ایم" پہلی اور دوسری صف کی لمبائی ہے۔

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

O (زیادہ سے زیادہ (ن ، ایم)) کہاں "این" اور "ایم" پہلی اور دوسری صف کی لمبائی ہے۔