Solution using Binary Search (Max Sum Combinations)


#1
bool pred(int mid, vector<int>& a, vector<int>& b, int x)
{
    int cnt=0;
    for(int i=0; i<a.size();i++)
    {
        int el = a[i];
        cnt+=upper_bound(b.begin(),b.end(),mid-el,greater<int>())-b.begin();
    }
    // cout<<mid<<" "<<cnt<<endl;
    return cnt>=x;
}
vector<int> Solution::solve(vector<int> &a, vector<int> &b, int x) 
{
    sort(a.begin(), a.end(), greater<int>());
    sort(b.begin(), b.end(), greater<int>());
    int n=a.size();
    int lo = a[n-1]+b[n-1];
    int hi = a[0]+b[0];
    int mid; //guess for the lowest number
    while(hi-lo>3)
    {
        mid=lo+(hi-lo)/2;
        bool ax = pred(mid,a,b,x);
        bool bx = pred(mid+1,a,b,x);
        if(ax and !bx) goto done;
        if(ax) lo=mid;
        else hi=mid;
    }
    for(int i=hi; i>=lo;i--)
    {
        if(pred(i,a,b,x))
        {
            mid=i;
            goto done;
        }
    }
    done:
    vector<int> ans;
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n;j++)
        {
            if(a[i]+b[j]<=mid) break;
            else ans.push_back(a[i]+b[j]);
        }
    }
    while(ans.size()!=x) ans.push_back(mid);
    sort(ans.begin(),ans.end(),greater<int>());
    return ans;
}

The complexity is O(nlognlogn)
Sort the two arrays.
The main idea is to find the smallest element of the required array.
This can be found using binary search. The predicate involved calculates “cnt” that is how many sum combinations have a sum>=mid in O(nlogn). If cnt>=x, then mid is a candidate for the smallest element of the array. Let’s store this finally in mid;
Once we know that, fill the answer vector with all sum combinations which are >mid . To complete the vector, fill it with mid;