دو ترتیب شدہ صفوں میں سے جوڑے گنیں جن کی رقم ایک دیئے گئے قدر x کے برابر ہے


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے بینک بازار سسکو درگ ہنیویل پی پی یو Roblox ٹیکسی 4 سوری Yandex
لڑی ہیش چھانٹ STL

مسئلہ یہ بیان

"دو سے جوڑے گنیں ترتیب دیا وہ اشارے جن کی رقم ایک دیئے گئے قدر x "کے مساوی ہے اس میں کہا گیا ہے کہ آپ کو اعداد کی دو ترتیب شدہ سرنی اور ایک عدد اعداد کا مجموعہ کہا جاتا ہے۔ مسئلہ بیان میں جوڑی کی کل تعداد معلوم کرنے کے لئے کہا گیا ہے جو ایک مقررہ قیمت کے برابر ہے۔

مثال کے طور پر

arr1[] = {1, 6, 8, 11}

arr2[] = {1, 3, 5, 9}

sum = 9
2

 

وضاحت: کیونکہ ایک دیئے گئے صف میں کل 2 جوڑے ہیں جو (6 ، 3) اور (8 ، 1) ہیں۔ کیونکہ دوسرے جوڑے کی رقم مطلوبہ رقم سے زیادہ یا کم ہوتی ہے۔

arr1[] = {3, 5, 11, 14};

arr2[] = {2, 4, 5, 11}

sum = 16
3

 

وضاحت: کیونکہ دیئے گئے صف میں کل 3 جوڑے ہیں جو (5 ، 11) ، (11 ، 5) ، اور (14 ، 2) ہیں۔

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

1. Set count and left to 0, and right to n-1 where n is the length of the array.
2. While left is less than m and right is greater than equal to 0, repeat the following the steps-
    1. If the sum of arr[left] and arr[right] is equal to the given value, then increase the value of count and left by 1 and decrease the value of right by 1.
    2. Else check if the addition of arr[left] and arr[right] is less than the given value sum, then increase the value of left by 1.
    3. Decrease the value of right by 1 if the addition is greater than the sum.
3. Return the count value after traversing the arrays.

وضاحت

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

ہم کی قیمت طے کرنے جارہے ہیں شمار 0 تک۔ کیوں کہ اگر ہم مطلوبہ جوڑی تلاش کرتے ہیں تو ہم گنتی کی اس قدر میں 1 اضافہ کریں گے۔ ایک جوڑی دو اقدار پر مشتمل ہوگی۔ یقینا. ، ہم یہ چیک کرنے جارہے ہیں کہ کیا اس جوڑے میں اس قدر کا اضافہ دیئے گئے قدر کے برابر ہے۔ اگر یہ سچ ہے تو ہم گنتی کی قدر میں 1 اضافہ کریں گے جبکہ لوپ اس انداز میں. تب یہ تب تک چلے گا جب تک ایم (ایم سرنی میں سے ایک کی لمبائی نہیں) اور r (جہاں r کسی صف کی لمبائی سے کم ہے) 0 کے برابر سے زیادہ نہیں ہوتا ہے۔

ایک لوپ میں ، ہم اس کی جانچ کریں گے کہ جوڑی کی قیمت دی گئی قیمت میں مزید اضافہ کرتی ہے۔ پھر ، جب بھی یہ حالت درست ہوجاتی ہے تو ہمیں ایک جوڑا مل جاتا ہے۔ اگر رقم دی گئی قیمت سے کم ہو تو ہم لوپ کو جاری رکھیں گے۔ پھر ہم کی قدر میں اضافہ کریں گے l 1 کے ذریعہ ہم صرف قدر کم کرتے ہیں r آخر 1. ، ہم گنتی کی قدر لوٹائیں گے۔

دو ترتیب شدہ صفوں میں سے جوڑے گنیں جن کی رقم ایک دیئے گئے قدر x کے برابر ہے

ضابطے

C ++ کوڈ جوڑے جوڑنے کے لئے جس کا جوڑا دو ترتیب شدہ صفوں سے x ہے

#include<iostream>

using namespace std;

int getPairofsum(int arr1[], int arr2[], int m, int n, int sum)
{
    int count = 0;
    int left = 0, right = n - 1;

    while (left < m && right >= 0)
    {
        if ((arr1[left] + arr2[right]) == sum)
        {
            left++;
            right--;
            count++;
        }
        else if ((arr1[left] + arr2[right]) < sum)
            left++;
        else
            right--;
    }
    return count;
}
int main()
{
    int arr1[] = {1, 6, 8, 11};
    int arr2[] = {1, 3, 5, 9};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    int sum = 9;
    cout << "Count = "<< getPairofsum(arr1, arr2, m, n, sum);
    return 0;
}
Count = 2

 

جاوا کوڈ جوڑے جوڑنے کے لئے جس کا جوڑا دو ترتیب شدہ اریوں سے x ہے

class PairofSum
{
    public static int getPairofsum(int arr1[],int arr2[], int m, int n, int sum)
    {
        int count = 0;
        int left = 0, right = n - 1;

        while (left < m && right >= 0)
        {
            if ((arr1[left] + arr2[right]) == sum)
            {
                left++;
                right--;
                count++;
            }
            else if ((arr1[left] + arr2[right]) < sum)
                left++;
            else
                right--;
        }
        return count;
    }
    public static void main (String[] args)
    {
        int arr1[] = {1, 6, 8, 11};
        int arr2[] = {1, 3, 5, 9};
        int m = arr1.length;
        int n = arr2.length;
        int sum = 9;
        System.out.println( "Count = "+ getPairofsum(arr1, arr2, m, n, sum));
    }
}
Count = 2

 

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

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

O (m + n) کہاں "ایم" اور "این" arr1 اور arr2 میں عناصر کی تعداد ہے۔ کیونکہ جس زیادہ سے زیادہ ہم سفر کرسکتے ہیں وہ m + n ہے۔

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

O (1) کیونکہ اضافی جگہ کی ضرورت نہیں ہے۔ اس طرح ایک مستقل جگہ پیچیدگی حاصل کی جاتی ہے۔