{"id":457,"date":"2020-06-10T10:50:56","date_gmt":"2020-06-10T10:50:56","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=457"},"modified":"2023-06-09T10:01:47","modified_gmt":"2023-06-09T10:01:47","slug":"total-number-of-sub-arrays-whose-sum-value-is-greater-than-or-equal-to-k","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/total-number-of-sub-arrays-whose-sum-value-is-greater-than-or-equal-to-k\/","title":{"rendered":"Find Number of Sub-arrays with sum is greater than or equal to K"},"content":{"rendered":"

\"\"<\/p>\n

Finding the number of subarrays with a sum greater than or equal to a given value K is a common problem in array manipulation. The task involves determining the count of contiguous subarrays within a given array where the sum of elements in the subarray meets the specified condition. This problem can be efficiently solved using approaches such as prefix sum or the two-pointers technique<\/p>\n

Given an array of N<\/code> elements, print the total number of sub-arrays whose sum value is greater than or equal to K<\/code>. Also, it is recommended to go through from Subarray with given sum<\/a> problem for better understanding.<\/p>\n

Understand with the Example:<\/h2>\n
Input : N = 5, K = 3\n        A[] = [1 2 3 4 5]\n\nOutput : 13\n\nExplanation :\n\nThere are 13 sub-arrays whose sum is greater than or equal to 3\n\n(3), (4), (5) \n\n(1 2), (2 3), (3 4), (4 5),\n\n(1 2 3), (2 3 4), (3 4 5), \n\n(1 2 3 4), (2 3 4 5), (1 2 3 4 5)\n\nThe only two sub-arrays whose sum is less than 3 are (1) and (2).<\/code><\/pre>\n
Brute Force Method to Find Number of Subarrays with Sum Greater than or Equal to K:<\/h2>\n
\n
    \n
  1. \n
    A simple brute force solution is to generate all the sub-arrays and check whether their sum is greater than or equal to K<\/code> or not.<\/p>\n<\/li>\n
  2. \n
    There are <\/p>\n
    <\/p>\n
    number of sub-arrays in an array.   <\/p>\n<\/li>\n
  3. \n
    Time Complexity<\/code> of this approach would be quadratic i.e. O(N^2)<\/code>.<\/p>\n<\/li>\n<\/ol>\n
    NOTE<\/strong>: If N <= 103<\/sup>, it would work fine but for greater values of N<\/code>, it would result in TLE (Time Limit Exceeded).<\/p>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n\t\t\t\t\t\t