Plz tell me the logic to solve this problem
Problem link
I found this answer on Quora by Raziman T.V.,
This problem can be solved in O(N \log N) per query using binary search.
The problem basically reduces to this:
Given an array of positive integers, what is the sum of the lowest K subarray sums?
Clearly, even generating all the subarray sums is going to take O(N^2), which we would like to avoid. We will overcome this limitation by not generating the subarrays at all but only dealing with their counts and sums. Turns out that this is actually possible to do!
Let the original array be ar[1…N]. We will start by defining the following arrays
-
psum[1…N] : psum[i] = ar[1] + ar[2] + … ar[i] = sum(ar[1…i])
-
qsum[1…N] : qsum[i] = N*ar[1] + (N-1)*ar[2] + … (N-i+1)*ar[i]
Using these arrays, subarray sums and sums of subarray sums can be computed quickly. Sum(ar[l…r]) is given by psum[r]-psum[l-1]. Similarly, sum(ar[l…l]) + sum(ar[l…(l+1)]) + … sum(ar[l…r]) = qsum[r]-qsum[l-1]-(N-r)(psum[r]-psum[l-1]).
With this, let us tackle the problem. We will solve the problem in two steps: First, we will find the value S of the Kth largest subarray sum. Then we will sum up all the subarrays with sum less than or equal to S.
For the first part, we use binary search. All subarray sums will be between 0 and psum[N]. For each x in the range, we want to ask the question : How many subarrays have sum less than or equal to x? We can check this by considering all starting points for the subarrays. From the starting point, we keep moving right till the sum overshoots x. Done naively, this would take O(N) time per starting point which is too much. We can reduce the complexity to O(\log N) per starting point by finding the limit by binary searching on the psum[] array. It is possible to reduce the complexity even further to amortised O(1) by a sliding window/two pointers algorithm. On increasing the value of x, the number of subarrays with sum less than or equal to x increases as well. Thus we can binary search for the value of x which gives exactly K sums (In fact you want to find the x which gives just under K sums and extrapolate the rest).
Once the value of x is found, we find the required subarray sum in the same fashion. For each starting point, the subarray limit can be found as earlier, using binary search or sliding window. The sum of subarray sums for the starting point can be calculated using the qsum[] array defined above.