Блог пользователя shivam565

Автор shivam565, история, 2 года назад, По-английски

How to find total number of subarrays with sum atmost k?

Constrains :
-1e4 <= a[i] <= 1e4
1 <= n <= 1e5

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

We can use sliding window technique to solve the problem.
Here, i and j represent starting and ending points of the sliding window.
Initially i = j = 0.
Now, we will traverse the whole array and try to add elements.

  • If sum < k, j++. So, number of sub-arrays produced = j-i. Also add arr[j] to the sum.
  • If sum >= k, we will subtract arr[i] from sum so that again sum<k. So, i++.
CODE
»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Convert the statement to it's equivalent in terms of prefix sums i.e $$$pre_r - pre_l <= k$$$.

Now iterating over $$$r$$$, we need to find number of $$$l$$$ such that $$$pre_l >= pre_r - k$$$, which can be computed using ordered set of all $$$pre_l$$$.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    but in this case, I have to iterate on all the prefix values >= pre(r)-k. How you will handle this thing while iterating the array?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      use pbds!

    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      You can use pbds or alternatively, compress the values of the prefix sum and use a data structure like segment tree or fenwick tree to count the values.