Given two arrays A and B of size N each, find the maximum N elements from the sum combination (A[i]+B[j]) formed elements A and B. You can only combine elements of two arrays you can\'t combine the same array elements

(1) Brute Force Approach:

In this approach, we will use a two-loop and iterate through all combinations of the elements and store them in a heap or a vector. If we are storing them in a max heap then we pop the top element from the heap n times since the top of the heap is the maximum sum elements and if we are storing sum combination in vector then we need to sort the vector and then we take n max sum combination from it.

The above logic can be implemented with the help of vector and priority_queue that is a heap data structure.

• Time Complexity for the above approach is O(n*n)
• Space Complexity for the above approach is O(n*n)

Program:

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

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of arrays: ";
        ll n;
        cin >> n;

        ll A[n], B[n];
        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++)
            cin >> A[i];

        for (ll i = 0; i < n; i++)
            cin >> B[i];

        //declare heap.
        priority_queue<ll> p;

        //iterate through outer loop A.
        for (ll i = 0; i < n; i++) {
            //iterate through inner loop B.
            for (ll j = 0; j < n; j++) {
                p.push(A[i] + B[j]);
            }
        }

        //declare vector to store make n max sum combination.
        vector<ll> v1;

        //iterate through n elements from heap.
        while (n--) {
            //store max elements and pop it from the heap.
            v1.push_back(p.top());
            p.pop();
        }

        //final max sum combination.
        for (ll i = 0; i < v1.size(); i++)
            cout << v1[i] << " ";
        cout << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter size of arrays: 4
Enter elements:
4 5 6 7
2 3 8 9
16 15 15 14 
Enter size of arrays: 3
Enter elements:
11 22 33
1 2 3
36 35 34 
Enter size of arrays: 5
Enter elements:
1 2 3 4 5
10 11 12 13 14   
19 18 18 17 17 

(2) Better Approach:

In this approach, we will use the priority queue with pairs and set for managing the indices that we have used that are remaining. We need to sort both the arrays and store their last elements in the max heap which we create with help of priority_queue and pairs.

priority_queue<pair<int, pair<int, int>>> heap, the first pair consists of sum and another pair for indices from which the sum has been obtained. To avoid the duplicacy of array elements we will use either a map or set with pairs. We need to repeat the process n times to get the maximum sum pairs, in each step we will check the indices pair {l,r-1} and {l-1,r} for storing it in the heap after processing the previous indices {l,r}.

• Time Complexity for the above case: O(Nlog(N)
• Space Complexity for above cases: O(N)

Program:

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

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of arrays: ";
        ll n;
        cin >> n;

        cout << "Enter elements :\n";
        ll A[n], B[n];
        for (ll i = 0; i < n; i++)
            cin >> A[i];
        for (ll i = 0; i < n; i++)
            cin >> B[i];

        //priority_queue(heap)with pair as its elements.
        priority_queue<pair<ll, pair<ll, ll> > > pq;

        //declare set with pairs to store indices pairs.
        set<pair<ll, ll> > st;

        //sort both the arrays.
        sort(A, A + n);
        sort(B, B + n);

        //push the first maximum element in the heap.
        pq.push({ (A[n - 1] + B[n - 1]), { n - 1, n - 1 } });

        //insert the indices pair in set.
        st.insert({ n - 1, n - 1 });

        //pair variable for further operations.
        pair<ll, pair<ll, ll> > p;
        //declare vector to store sum combination in it.
        vector<ll> v1;

        while (n--) {
            //take the maximum sum combination from heap.
            p = pq.top();
            pq.pop();
            ll l = p.second.first; //store A[] array index in l.
            ll r = p.second.second; //store B[] array index in r.
            v1.push_back(p.first); //store sum in vector.

            //check for other cases as second last indices and
            //list indices from the {l,r}
            if (l > 0 and r >= 0 and st.find({ l - 1, r }) == st.end()) {
                st.insert({ l - 1, r });
                pq.push({ (A[l - 1] + B[r]), { l - 1, r } });
            }
            if (l >= 0 and r > 0 and st.find({ l, r - 1 }) == st.end()) {
                st.insert({ l, r - 1 });
                pq.push({ (A[l] + B[r - 1]), { l, r - 1 } });
            }
        }

        cout << "Final result: ";
        for (ll i = 0; i < v1.size(); i++)
            cout << v1[i] << " ";
        cout << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 2
Enter size of arrays: 4
Enter elements :
1 2 3 4
10 9 8 7
Final result: 14 13 13 12 
Enter size of arrays: 5
Enter elements :
1 2 3 4 5
11 22 33 44 55
Final result: 60 59 58 57 56