Question

De-Shaw | OA Coding Questions and Solutions | Codepair | Set - 9 | 2022

Answer 1

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);
}