ਦੋ ਕ੍ਰਮਬੱਧ ਐਰੇ ਵਿੱਚੋਂ ਜੋੜ ਗਿਣੋ, ਜਿਨ੍ਹਾਂ ਦੀ ਜੋੜ ਇੱਕ ਦਿੱਤੇ ਮੁੱਲ x ਦੇ ਬਰਾਬਰ ਹੈ  


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ BankB बाजार ਨੂੰ Cisco ਕਿਲੇ ਹਨੀਵੈੱਲ ਪਉਯੂ ਰੋਬਲੌਕਸ ਟੈਕਸੀ 4 ਸੂਅਰ ਯੈਨਡੇਕਸ
ਅਰੇ ਹੈਸ਼ ਲੜੀਬੱਧ 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 ਨਾਲ ਵਧਾ ਦੇਵਾਂਗੇ ਲੂਪ ਦੌਰਾਨ ਇਸ inੰਗ ਨਾਲ. ਤਦ ਇਹ ਉਦੋਂ ਤਕ ਜਾਏਗਾ ਜਦੋਂ ਤੱਕ m (m ਐਰੇ ਦੇ ਇੱਕ ਦੀ ਲੰਬਾਈ ਨਹੀਂ) ਅਤੇ 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

 

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ  

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਮ + ਐਨ) ਜਿੱਥੇ ਕਿ "M" ਅਤੇ “ਐਨ” arr1 ਅਤੇ arr2 ਵਿੱਚ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਵੱਧ ਤੋਂ ਵੱਧ ਸਫ਼ਰ ਕਰ ਸਕਦੇ ਹਾਂ m + n.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1) ਕੋਈ ਵਾਧੂ ਜਗ੍ਹਾ ਦੀ ਲੋੜ ਹੈ ਦੇ ਰੂਪ ਵਿੱਚ. ਇਸ ਤਰ੍ਹਾਂ ਇੱਕ ਨਿਰੰਤਰ ਸਪੇਸ ਗੁੰਝਲਤਾ ਪ੍ਰਾਪਤ ਕੀਤੀ ਜਾਂਦੀ ਹੈ.