uttamkumarreddy123's blog

Need Help In solving this question.
By uttamkumarreddy123, history, 5 months ago, In English

You are given an array A of size N.

Let B denote the list of all N*(N+1)/2 subarray sums of A sorted in non-increasing order.

Your task is to return the Kth element in B. Since the answer can be very large return it modulo 10+7

1<=N<=10**5 1<=K<=min(N*(N+1)/2,10**5) 1<=a[i]<=10**9

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

apply binary search for a given mid calculate no of subarrays with sum<=mid which can be done using sliding window. now if no of such subarrays>=k then update ans=mid, high=mid-1 else low=mid

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is given mid you are referring above and calculate the no of sub arrays with sum required all sub arrays which are O(n2) results to TLE

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      mid is variable for binary search

      int low=0,high=1e15;

      int ans=-1;

      while(low<=high) {

      int mid=(low+high)/2;

      if(check(mid)>=k)

      { ans=mid;

      high=mid-1;}

      else low=mid+1;

      }

      check (mid) represent number of subarray with sum less than or equal to mid you can calculate this in O(n)

      refer this

      → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This can be easily solved using binary search and two pointers. For a value $$$VAL$$$, it doesn't require $$$O(N^2)$$$ to count all the subarrays that have $$$sum <= VAL$$$, but rather $$$O(N)$$$ or $$$O(N log N)$$$ . Define $$$sum(l,r) = a[l] + ... +a[r]$$$. It's obvious that if $$$ly$$$ $$$<=$$$ $$$lx$$$ $$$<=$$$ $$$rx$$$ $$$<=$$$ $$$ry$$$) then $$$sum(lx,rx)$$$ $$$<=$$$ $$$sum(ly,ry)$$$. Define $$$next[p]$$$ as the maximum value $$$p <= n$$$ such that $$$sum(p,next[p]) <= VAL$$$ . The number of subarrays satisfy the conditions will be $$$\sum_{p=1}^{n} next[p] - p + 1$$$. It's obvious that $$$next[p] <= next[p + 1]$$$, so the values $$$next[p]$$$ for the whole array can be calculated in $$$O(N)$$$ using two pointers or binary search. The overall complexity is $$$O(N log^2 sum)$$$ or $$$O(N log sum)$$$

→ Reply