Find Number of Sub-arrays with sum is greater than or equal to K

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

Understand with the Example:

Input : N = 5, K = 3
        A[] = [1 2 3 4 5]

Output : 13

Explanation :

There are 13 sub-arrays whose sum is greater than or equal to 3

(3), (4), (5) 

(1 2), (2 3), (3 4), (4 5),

(1 2 3), (2 3 4), (3 4 5), 

(1 2 3 4), (2 3 4 5), (1 2 3 4 5)

The only two sub-arrays whose sum is less than 3 are (1) and (2).

Brute Force Method to Find Number of Subarrays with Sum Greater than or Equal to K:

1. A simple brute force solution is to generate all the sub-arrays and check whether their sum is greater than or equal to K or not.

2. There are

   

   number of sub-arrays in an array.

3. Time Complexity of this approach would be quadratic i.e. O(N^2).

NOTE: If N <= 10³, it would work fine but for greater values of N, it would result in TLE (Time Limit Exceeded).

SOLUTIONS:

#include <stdio.h> 

int subarrays(int arr[],int n,int k) 
{ 
    int count = 0; 

    for (int i = 0; i < n; i++) 
    { 
      int sum = 0; 
      for (int j = i; j < n; j++) 
      {
        sum += arr[j];
        if (sum  >= k) 
        { 
            count++; 
        } 

      } 
    } 

    return count; 
} 

int main() 
{ 
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,k;
    scanf("%d %d",&n,&k);
    int arr[n];
    for(int i=0;i<n;i++)
      scanf("%d",&arr[i]);
    printf("%d\n",subarrays(arr,n,k));
  }
} 

#include <bits/stdc++.h> 
using namespace std; 


int subarrays(int arr[],int n,int k) 
{ 
    int count = 0; 

    for (int i = 0; i < n; i++) 
    { 
      int sum = 0; 
      for (int j = i; j < n; j++) 
      {
        sum += arr[j];
        if (sum  >= k) 
        { 
            count++; 
        } 

      } 
    } 

    return count; 
} 

int main() 
{ 
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];
    cout<<subarrays(arr,n,k)<<"\n";
  }
  return 0;
}

Time Complexity: O(N²)

Space Complexity: O(1)

Efficient Method to Find Number of Subarrays with Sum Greater than or Equal to K:

1. In order to find the total no. of subarrays that have sum value greater than equal to K, instead we can find total subarrays that have value less than K, the difference between total no of subarrays and our calculated subarrays would be our answer.

2. The idea is to use Sliding Window Technique.

3. We make use of two pointers that point to the starting and the ending of this window, start and end.

4. Initially both the pointers point to the beginning of the array i.e. 0^th index.

5. Now whenever we add an element, there arises two possible cases –
   >1. If the sum is less than K, we will increment our end pointer by 1 and the value of (end - start) will give us the current count of subarrays with value less than K. Because there are as many subarrays as the length of the window.
   >
   >2. If the sum is greater than or equal to K, we need to subtract the starting element from the sum so that it becomes less than K again and increment our start pointer by 1.
   >
   >3. Keep repeating steps 1 and 2 until we reach the end of the array.

Program to find number of subarrays with sum greater than k or Equal to K:

A[] = [1, 2, 3, 4, 5]
K = 3

start = 0
end = 0
sum = A[start] = 1
count = 0

(start < n) and (end < n) and (sum < K) 
end ++ => end = 1
count = count + (end - start) = 0 + 1 - 0 = 1
sum = sum + A[end] = 1 + 2 = 3
start = 0

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = 3 - 1 = 2
start ++ => start = 1
end = 1

(start < n) and (end < n) and (sum < K) 
end ++ => end = 2
count = count + (end - start) = 1 + 2 - 1 = 2
sum = sum + A[end] = 2 + 3 = 5
start = 1

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = 5 - 2 = 3
start ++ => start = 2
end = 2

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = 3 - 3 = 0
start ++ => start = 3
end = 2

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = 0 - 4 = -4
start ++ => start = 4
end = 2

(start < n) and (end < n) and (sum >= K) 
sum = sum - A[start] = -4 - 5 = -9
start ++ => start = 5
end = 2

Since (start >= n), we will stop here and count = 2 is the number of subarrays
which have value less than K = 3

Count of subarrays with sum greater than or equal to K can be calculated by subtracting this calculated count by total number of sub-arrays.

SOLUTIONS:

#include <stdio.h>

int kmin(int arr[],int n,int k)
{
  int start = 0, end = 0, sum = arr[0], count = 0;
  while(start<n && end<n)
  {
    if(sum<k)
    {
      end++;
      if(end>=start)
        count += end-start;
      if(end<n)
        sum += arr[end];
    }
    else
    {
      sum -= arr[start];
      start++;
    }
  }
  return count;
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,k;
    scanf("%d%d",&n,&k);
    int arr[n];
    for(int i=0;i<n;i++)
    {
      scanf("%d",&arr[i]);
    }
    long long res = ((long long)n*(n+1))/2;
    printf("%lld\n",res-kmin(arr,n,k));
  }

  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int kmin(int arr[],int n,int k)
{
  int start = 0, end = 0, sum = arr[0], count = 0;
  while(start<n && end<n)
  {
    if(sum<k)
    {
      end++;
      if(end>=start)
        count += end-start;
      if(end<n)
        sum += arr[end];
    }
    else
    {
      sum -= arr[start];
      start++;
    }
  }
  return count;
}
int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n,k;cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
    {
      cin>>arr[i];
    }
    long long res = ((long long)n*(n+1))/2;
    cout<<res-kmin(arr,n,k)<<"\n";
  }

  return 0;
}

import java.util.*;
import java.io.*;


public class Main {

  public static long kmin(int arr[],int n,int k)
    {
      int start = 0, end = 0, sum = arr[0], count = 0;
      while(start<n && end<n)
      {
        if(sum<k)
        {
          end++;
          if(end>=start)
            count += end-start;
          if(end<n)
            sum += arr[end];
        }
        else
        {
          sum -= arr[start];
          start++;
        }
      }
      return count;
}
  public static void main(String args[]) throws IOException {

    int t;
        Scanner sc=new Scanner(System.in);
        t=sc.nextInt();

        while(t>0){
            int n,k;
            n=sc.nextInt();
            k=sc.nextInt();
            int arr[]=new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=sc.nextInt();
            }
            long res = (n*(n+1))/2;
            long p=kmin(arr,n,k);
            System.out.println(res-p);
            t--;
      }
  }
}

This article tried to discuss Sliding Window Technique. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming.

Related topics:

• Missing number in array
• Convert string to array