Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
687 views
in Online Assessments by Expert (113,480 points) | 687 views

1 Answer

0 like 0 dislike
Best answer
We are given 4 Lists of Integers. Our task is to find number of unique combinations possible, that have sum>=k
Condition is you can pick exactly one element from each of the list..

This is pretty similar to 4 sum problem with the condition that there are 4 lists instead of 1 of varying sizes.

How can we use binary search in this ?


O ((n^2)*logn) approach

compute all possible sum with two elements from Array 1 and Array 2: O(n^2)
sort the above sum array: O(klogk) where k = n^2
form the second set of sums using Array 2 and Array 3. And while forming check for lower bound of this sum in first set of sums created in step 1. And since the sum array is sorted, if we substract the lower bound index from the end index and add to the total number of permutations, we'll get the answer.
#include<bits/stdc++.h>

using namespace std;

struct cmp {
    bool operator() (const pair<int, pair<int,int>> & left, const pair<int, pair<int,int>> & right)
    {
        return left.first < right.first;
    }
    bool operator() (const pair<int, pair<int,int>> & left, int right)
    {
        return left.first < right;
    }
    bool operator() (int left, const pair<int, pair<int,int>> & right)
    {
        return left < right.first;
    }
};
    

int computePermutations(vector<int> &arr1, vector<int> &arr2, vector<int> &arr3, vector<int> &arr4, int k) {
    vector<pair<int, pair<int,int>>> sums;
    for (int i=0; i<arr1.size(); i++) {
        for (int j=0; j<arr2.size(); j++) {
            sums.push_back({arr1[i]+arr2[j], {i,j}});
        }
    } // O(n^2)
    
    sort(sums.begin(), sums.end()); // O(2*(n^2)*logn)
    
    int ans = 0;
    for (int i=0; i<arr3.size(); i++) {
        for (int j=0; j<arr4.size(); j++) {
            int sum = arr3[i] + arr4[j];
            // sum + sums[idx] >= k
            // sums[idx] >= k - sum
            auto idx = lower_bound(sums.begin(), sums.end(), k-sum, cmp());
            // first element which has value not less than k-sum
            ans += sums.end() - idx;
        }
    }
    // cout << "Answer: "<<ans<<endl;
    return ans;
}

int main() {
    vector<int> arr1 = {1,2,3};
    vector<int> arr2 = {4,5,6,7};
    vector<int> arr3 = {8,9,10,11,12};
    vector<int> arr4 = {13,14,15,16,17,18,19};
    int  k = 40;
    computePermutations(arr1, arr2, arr3, arr4, k);
}
by Expert (113,480 points)