# Simple C++ O(Clog(C)) solution

#1

// Code by Prateek Mishra IIT2018199, IIIT Allahabad.

//UNDERSTANDING THE APPROACH
/* We here use the concept of merging k - sorted linked lists.
Let the given vectors after sorting be
A : 16, 11, 7, 1
B : 15, 10, 9, 2

Now we know that 4 ^ 4 different sums are possible for this combination and we need to
find the largest C out of these. Let the pairs be:
(16,15), (16,10), (16,9), (16,2),
(11,15), (11,10), (11,9), (11,2),
(7,15), (7,10), (7,9), (7,2),
(1,15), (1,10), (1,9), (1,2),

Note that the numbers (pair of the sums) in every row are sorted in descending order. Now we
need to merge these sorted LinkedLists.
*/

``````vector<int> Solution::solve(vector<int> &A, vector<int> &B, int C)
{
sort(A.rbegin(), A.rend());
sort(B.rbegin(), B.rend()); //sorting both the lists in descending order.
priority_queue<pair<int, pair<int, int>>> maxh; //max heap for storing (sum, (i - index, j - index))

for (int i = 0; i < C; i++) //pushing the heads of all the linked lists.
{
maxh.push(make_pair(B[0] + A[i], make_pair(0, i)));
}

std::vector<int> ans;
while(ans.size() < C)
{
auto maxele = maxh.top(); maxh.pop();
ans.emplace_back(maxele.first); //pushing the top to ans and inserting head -> next.
maxh.push(make_pair(B[maxele.second.first + 1] + A[maxele.second.second], make_pair(maxele.second.first + 1, maxele.second.second)));
}
return ans;
}``````

#2

great approach and well written., thanks!

#3

Same Merge sorted list approach as above, concise C++ code

``````vector<int> Solution::solve(vector<int> &A, vector<int> &B, int C) {
vector<int>res;
priority_queue<tuple<int, int, int>>q;
sort(A.rbegin(), A.rend());
sort(B.rbegin(), B.rend());
for(int i=0; i<C; i++) {
q.push({A[i]+B[0], i, 0});
}
while(res.size()<C) {
auto [sum, i, j] = q.top(); q.pop();
res.push_back(sum);
q.push({A[i]+B[j+1], i, j+1});
}
return res;
}``````

#4

This one is short and crisp.
Nice, Shot Champâ€¦