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:
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.There are
number of sub-arrays in an array.
Time Complexity
of this approach would be quadratic i.e.O(N^2)
.NOTE: If N <= 103, 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(N2)
Space Complexity: O(1)
Efficient Method to Find Number of Subarrays with Sum Greater than or Equal to K:
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 thanK
, the difference between total no of subarrays and our calculated subarrays would be ouranswer
.The idea is to use
Sliding Window Technique
.We make use of two pointers that point to the starting and the ending of this window,
start
andend
.Initially both the pointers point to the beginning of the array i.e. 0th index.
Now whenever we add an element, there arises two possible cases –
>1. If the sum is less thanK
, we will increment ourend
pointer by1
and the value of (end
-
start
) will give us the current count of subarrays with value less thanK
. Because there are as many subarrays as the length of the window.
>
>2. If the sum is greater than or equal toK
, we need to subtract the starting element from the sum so that it becomes less thanK
again and increment ourstart
pointer by1
.
>
>3. Keep repeating steps1
and2
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--; } } }
Space Complexity:
O(1)
[forminator_quiz id="488"]
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: