You are given 4 arrays of N size each. At a time u can take 1 value from each of the 4 arrays to form a quadruplet. How many quadruplets exist such that the sum of the quadruplet is less than or equal to M.
Constraints:-
1<=1000<=N
-10^5<=A[i]<=10^5
M<=10^9
perhaps u can provide the question link or what is the range of M ?
This question was asked in DE Shaw campus placement so i cant give the exact link but the question was more or less this.
https://www.geeksforgeeks.org/count-quadruples-four-sorted-arrays-whose-sum-equal-given-value-x/
This might help you
This method is good if u want the quadruplet to be exactly M but not for <=M as hashing can only lookup exact values in O(1) time and not how many values<= M in the hashmap.
For how many values are smaller than equal to some other value we usually use an order statistics tree. It is an augmented BST that stores the size of the subtree in each node. It can calculate the required value in logn. It is known as ordered set and exists in PBDS in C++(only in GCC).
As N <= 1000,
Store the sum of each pair of element from A and B in O(n^2) in a vector. Similarly, store the sum of each pair of elements from C to D in O(n^2) in another vector. Sort both the vectors(say they are sum1 and sum2). Now iterate over the values of sum1 and binary search the number of values less than M-sum1[i] in sum2 and keep adding it in answer.
Total complexity : O(N^2 log(n^2))
My approach was to enter all the values of the array(s) in a map and later sort them, then iterate through them and add the consecutive element until m>sum
and then iterate again but from n-i-1 where n is the number of element and so on;
also, the brute force approach was to get all elements and then push them all to a vector and sort them using vector fn
later use 2 loops and approach the problem as it was a subarray problem ie:
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=0;j<n-i;j++)
{
sum+=a[j];
}
if(sum<m)
{count++;}
}
here n is vector.size()+1;
So we should store the elements of each of the array as a subtree??
Kindly explain your approach a bit more in detail, sounds interesting.
You can calculate the pairwise sum for two arrays (Suppose first 2) in a vector in sorted format so that you can find the number of pairs less than a given sum using the lower bound, and iterate on the other two, while iterating just calculate the sum of the current two and check in vector the pairs will less sum , do this for all the pairs of array 3 and 4.
Time complexity : O(N x N x log(N))
space complexity : O(N*N)
This solution will pass, still if better solution exists , please comment down.
I finally got it. It can be solved using DP by memoizing for the sum.