Броји парове из два сортирана низа чији је збир једнак датој вредности к


Ниво тешкоће Лако
Често питани у БанкБазаар Цисцо Цитадела Хонеивелл ПаиУ роблок Таки4Суре иандек
Ред Хасх сортирање ЛИС

Изјава о проблему

„Броји парове од два сортирано низови чија је сума једнака датој вредности к ”проблем наводи да су вам дата два сортирана низа целих бројева и целобројна вредност која се назива сум. Изјава о проблему тражи да се сазна укупан број пара који сажима до дате вредности.

Пример

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).

Алгоритам за бројање парова из два сортирана низа чији је збир једнак датој вредности к

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. Покренућемо а док петља на овај начин. Тада ће ићи док вредности м (м је дужина једног поља) и р (где је р једна мања од дужине низа) не буду веће од једнаке 0.

У петљи ћемо проверити да ли се вредност пара збраја са датом вредношћу. Тада смо пронашли један пар кад год се ово стање оствари. Петљу ћемо наставити ако је збир мањи од задате вредности. Тада ћемо повећати вредност l за 1 друго само смањујемо вредност r до 1. На крају ћемо вратити вредност цоунт.

Броји парове из два сортирана низа чији је збир једнак датој вредности к

код

Ц ++ код за бројање парова чији је збир к из два сортирана низа

#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

 

Јава код за бројање парова чији је збир к из два сортирана низа

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

 

Анализа сложености

Сложеност времена

О (м + н) где "М"   „Н“ је број елемената у арр1 и арр2. Јер максимум који можемо путовати је м + н.

Сложеност простора

О (1) јер није потребан додатни простор. Тако се постиже стална сложеност простора.