दो क्रमबद्ध सरणियों से योग x वाले जोड़ों की गणना - C++

समस्या विवरण

हमें दो धनात्मक संख्याओं वाली सरणियाँ और एक मान x दिया गया है। लक्ष्य उन जोड़ों (A,B) की गणना करना है जहाँ A पहली सरणी से, B दूसरी सरणी से है, और A+B=x।

उदाहरण

इनपुट: arr_1[] = {1,2,5,3,4}, arr_2[] = {7,0,1,3}, x=6

आउटपुट: 2

व्याख्या: (5,1) और (3,3)

इनपुट: arr_1[] = {1,1,1}, arr_2[] = {2,2}, x=3

आउटपुट: 2

दृष्टिकोण

साधारण: दो नेस्टेड लूप से सभी जोड़े जाँचें। समय: O(n*m)।

कुशल: पहली सरणी के तत्वों को unordered_set में डालें। दूसरी सरणी को पार करें: प्रत्येक arr_2[j] के लिए यदि x - arr_2[j] सेट में है तो गणना बढ़ाएँ। समय: O(n+m)।

C++ कार्यान्वयन (कुशल)

#include <bits/stdc++.h>
using namespace std;

int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x) {
    int count = 0;
    unordered_set hash_map;
    
    for (int i = 0; i < size_arr_1; i++) hash_map.insert(arr_1[i]);
    
    for (int j = 0; j < size_arr_2; j++) {
        if (hash_map.find(x - arr_2[j]) != hash_map.end())
            count++;
    }
    return count;
}

int main() {
    int arr_1[] = {1, 2, 3, 4};
    int arr_2[] = {2, 3, 4, 5};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int x = 6;
    cout << "Count: " << Pair_value_x(arr_1, arr_2, size_arr_1, size_arr_2, x);
    return 0;
}

आउटपुट

Count: 4