Cəmi verilən x-a bərabər olan iki sıralanmış massivdən cütləri sayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur BankBazaar Cisco Citadel Honeywell PayU ROBLOX Taksi4Sure Yandex
Geyim Sükut çeşidləyici STLBaxılıb 37

Problem bəyanat

“İki cütdən say sıralandı cəmi verilmiş bir x-a bərabər olan massivlər ”problemi sizə iki ədəd sıralanmış tam ədəd və cəmi adlı bir tam dəyər verildiyini bildirir. Problem ifadəsi, verilən bir dəyərə qədər olan cütün ümumi sayını tapmağı xahiş edir.

misal

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

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

sum = 9
2

 

İzahat: Verilən bir sıra içərisində (2, 6) və (3, 8) cəmi 1 cüt olduğu üçün. Çünki digər cütlərin cəmi tələb olunan cəmdən daha çox və ya daha azdır.

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

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

sum = 16
3

 

İzahat: Verilən massivdə (3, 5), (11, 11) və (5, 14) olan cəmi 2 cüt olduğu üçün.

Cəmi verilən x-a bərabər olan iki sıralanmış massivdən cütlərin sayılması alqoritmi

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.

Izahat

Sizə iki çeşidlənmiş tam ədəd verilir seriallar və cəmi adlanan bir tam dəyər. Və verilmiş bir dəyərə qədər cəmi neçə mümkün cüt qurulacağını öyrənməyimiz istənir. Beləliklə, ikili axtarış metodu kimi oxşar bir texnikadan istifadə edəcəyik. Giriş dəyərlərini artan qaydada götürməyimizin səbəbi də budur. Bu şəkildə bu sualı həll edərkən bu texnikanı tətbiq edə biləcəyik. Əks təqdirdə serialı sıralayardıq.

Dəyərini təyin edəcəyik saymaq 0-a. Çünki lazımi cütü tapsaq sayımın dəyərini 1 artıracağıq. Bir cüt iki dəyərdən ibarət olacaq. Əlbəttə ki, bu dəyərin bir cütə əlavə edilməsinin verilmiş dəyər cəminə bərabər olub olmadığını yoxlayacağıq. Doğrudursa saymanın dəyərini 1 artıracağıq döngə zamanı bu şəkildə. Sonra m (m bir sıra uzunluğundadır) və r (burada r bir sıra uzunluğundan bir azdır) dəyərləri 0-a bərabər olana qədər gedəcəkdir.

Bir döngədə, cütün dəyərinin verilmiş dəyərə əlavə edib-etmədiyini yoxlayacağıq. Bu şərt nə vaxt gerçəkləşsə, onda bir cüt tapdıq. Cəmi verilən dəyərdən az olduqda döngəni davam etdirəcəyik. O zaman dəyərini artıracağıq l başqa 1 ilə yalnız dəyərini azaldırıq r ilə 1. Sonda saymanın dəyərini qaytaracağıq.

Cəmi verilən x-a bərabər olan iki sıralanmış massivdən cütləri sayınPin

Kodu

C ++ kodu cəmi iki sıralanmış massivdən x olan cütləri saymaq üçün

#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

 

Cəmi iki sıralanmış massivdən x olan cütləri saymaq üçün Java kodu

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ürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (m + n) hara "M" və "N" arr1 və arr2-dəki elementlərin sayıdır. Çünki səyahət edə biləcəyimiz maksimum m + n-dir.

Kosmik Mürəkkəblik

O (1) əlavə yer tələb olunmadığı üçün. Beləliklə daimi bir kosmik mürəkkəbliyə nail olur.

Translate »