Count Subarrays with product of sum and subarray length less than K
Given an array of positive elements arr[] of length N, the task is to count all the subarrays such that the product of the subarray sum and length of the subarray should be strictly less than K.
Examples:
Input: arr[] = {6, 2, 1, 4, 3}, K = 10
Output: 6
Explanation: There are six valid subarrays: {6}, {2}, {1}, {4}, {3}, {2, 1}Input: arr[] = {1, 4, 3}, K = 5
Output: 3
Naive Approach:
Generate all the subarray and calculate the product of sum and length of the subarray, if it is strictly less than K then increment the count by 1. Finally return the count.
Follow the steps below to implement the above idea:
- Iterate over all the subarray
- Calculate the sum of the current subarray and its length
- Check if the product of sum and length is strictly less than K
- If true, increment the count by 1.
- Finally, return the count.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int countSubarrays(vector< int >& arr, int K) { int n = arr.size(); int count = 0; // Iterate over all the subarray for ( int i = 0; i < n; i++) { long long sum = 0; for ( int j = i; j < n; j++) { // Calculate the sum of current subarray and its // length sum += arr[j]; int len = j - i + 1; // Check if product of sum and length is // strictly less than K If true, increment the // count by 1. if (sum * len < K) count++; } } // Finally, return the result. return count; } // Driver's code int main() { vector< int > arr = { 6, 2, 1, 4, 3 }; int K = 10; int result = countSubarrays(arr, K); cout << result << endl; return 0; } // This code is contributed by hkdass001 |
Java
public class Main { // Driver's code public static void main(String[] args) { int [] arr = { 6 , 2 , 1 , 4 , 3 }; int K = 10 ; int result = countSubarrays(arr, K); System.out.println(result); } public static int countSubarrays( int [] arr, int K) { int n = arr.length; int count = 0 ; // Iterate over all the subarray for ( int i = 0 ; i < n; i++) { long sum = 0 ; for ( int j = i; j < n; j++) { // Calculate the sum of current subarray and // its length sum += arr[j]; int len = j - i + 1 ; // Check if product of sum and length is // strictly less than K If true, increment // the count by 1. if (sum * len < K) count++; } } // Finally, return the result. return count; } } // This code is contributed by Tapesh(tapeshdua420) |
Python3
def countSubarrays(arr, K): n = len (arr) count = 0 # Iterate over all the subarray for i in range (n): sum = 0 for j in range (i, n): # Calculate the sum of current subarray and its # length sum + = arr[j] length = j - i + 1 # Check if product of sum and length is # strictly less than K If true, increment the # count by 1. if sum * length < K: count + = 1 # Finally, return the result. return count # Driver's code arr = [ 6 , 2 , 1 , 4 , 3 ] K = 10 result = countSubarrays(arr, K) print (result) # This code is contributed by Tapesh(tapeshdua420) |
C#
using System; class Program { // Driver's code static void Main( string [] args) { int [] arr = { 6, 2, 1, 4, 3 }; int K = 10; int result = countSubarrays(arr, K); Console.WriteLine(result); Console.ReadLine(); } private static int countSubarrays( int [] arr, int K) { int n = arr.Length; int count = 0; // Iterate over all the subarray for ( int i = 0; i < n; i++) { long sum = 0; for ( int j = i; j < n; j++) { // Calculate the sum of current subarray and // its length sum += arr[j]; int len = j - i + 1; // Check if product of sum and length is // strictly less than K If true, increment // the count by 1. if (sum * len < K) count++; } } // Finally, return the result. return count; } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
function countSubarrays(arr, K) { let n = arr.length; let count = 0; // Iterate over all the subarray for (let i = 0; i < n; i++) { let sum = 0; for (let j = i; j < n; j++) { // Calculate the sum of current subarray and its // length sum += arr[j]; let len = j - i + 1; // Check if product of sum and length is // strictly less than K If true, increment the // count by 1. if (sum * len < K) count++; } } // Finally, return the result. return count; } // Driver's code let arr = [ 6, 2, 1, 4, 3 ]; let K = 10; let result = countSubarrays(arr, K); console.log(result); // This code is contributed by akashish__ |
6
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved using Two Pointer or Sliding Window Technique based on the following idea:
Keep two variables start and end, to represent the starting and ending position of any window.
- If the current window is a valid subarray then all the possible subarrays that ends at the ending index of the current window is a possible subarray. This number is the same as the length of the current window.
- If the current window is not a valid subarray then shrink the window. Keep adding all valid subarray into the result and finally return it.
Follow the steps below to implement the above idea:
- Initialize start = 0, end = 0, to represent the starting and ending position of the subarray
- Initialize a variable sum = 0, which represents the sum of elements in the current window.
- Initialize a variable result = 0 to keep track of the answer.
- While the end is less than N, do the following
- Add the element to sum.
- Calculate the length of the current window
- Check if sum * length ? K i.e., if the current window is not valid.
- Do the following until the current window becomes valid:
- Remove the contribution of the element at the starting position.
- Shift the start by 1.
- Decrement the current window length by 1.
- Check if the current window is a valid subarray:
- If true, add (end ā start + 1) to result
- Shift the end by 1
- Do the following until the current window becomes valid:
- Otherwise, Include the (end ā start + 1) into the result and shift the end by 1
- Finally, return the result.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the count of the subarrays long long countSubarrays(vector< int >& arr, long long k) { long long n = arr.size(); // Initialise start = 0, end = 0, to // represent the starting and ending // position of the subarray long long start = 0, end = 0; // Initialise a variable sum, which // represent the sum of elements in the // current element. long long sum = 0; // Initialise a variable result to // keep track of answer. long long result = 0; // While end is less than size of array while (end < n) { sum += arr[end]; int len = end - start + 1; // Check if current window // is not valid if (sum * len >= k) { // Until current window // is not valid while (sum * len >= k) { // Remove the calculation // of element at start // position sum -= arr[start]; start++; len--; } // Check if current window // is valid subarray if (sum * len < k) { // If true, add (end - start + 1) // into result result += end - start + 1; } end++; } // Otherwise, Include the (end - start + 1) // into result and shift the // end by 1 else { result += end - start + 1; end++; } } // Finally, return the result return result; } // Driver code int main() { vector< int > arr = { 6, 2, 1, 4, 3 }; int K = 10; // Function Call cout << countSubarrays(arr, K); return 0; } // This code is contributed by hkdass001 |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the count of the subarrays static int countSubarrays( int [] arr, int k) { int n = arr.length; // Initialise start = 0, end = 0, to // represent the starting and ending // position of the subarray int start = 0 , end = 0 ; // Initialise a variable sum, which // represent the sum of elements in the // current element. int sum = 0 ; // Initialise a variable result to // keep track of answer. int result = 0 ; // While end is less than size of array while (end < n) { sum += arr[end]; int len = end - start + 1 ; // Check if current window // is not valid if (sum * len >= k) { // Until current window // is not valid while (sum * len >= k) { // Remove the calculation // of element at start // position sum -= arr[start]; start++; len--; } // Check if current window // is valid subarray if (sum * len < k) { // If true, add (end - start + 1) // into result result += end - start + 1 ; } end++; } // Otherwise, Include the (end - start + 1) // into result and shift the // end by 1 else { result += end - start + 1 ; end++; } } // Finally, return the result return result; } public static void main(String[] args) { int [] arr = { 6 , 2 , 1 , 4 , 3 }; int K = 10 ; // Function call System.out.print(countSubarrays(arr, K)); } } // This code is contributed by lokeshmvs21. |
Python3
# Python code to implement the approach # Function to find the count of the subarrays def countSubarrays(arr, k): n = len (arr) # Initialise start = 0, end = 0, to # represent the starting and ending # position of the subarray start = 0 end = 0 # Initialise a variable sum, which # represent the sum of elements in the # current element. sum = 0 # Initialise a variable result to # keep track of answer. result = 0 # While end is less than size of array while end < n: sum + = arr[end] length = end - start + 1 # Check if current window # is not valid if sum * length > = k: # Until current window # is not valid while sum * length > = k: # Remove the calculation # of element at start # position sum - = arr[start] start + = 1 length - = 1 # Check if current window # is valid subarray if sum * length < k: # If true, add (end - start + 1) # into result result + = end - start + 1 end + = 1 # Otherwise, Include the (end - start + 1) # into result and shift the # end by 1 else : result + = end - start + 1 end + = 1 # Finally, return the result return result # Driver code if __name__ = = '__main__' : arr = [ 6 , 2 , 1 , 4 , 3 ] K = 10 # Function Call print (countSubarrays(arr, K)) # This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code to implement the approach using System; class GFG { // Function to find the count of the subarrays static int countSubarrays( int [] arr, int k) { int n = arr.Length; // Initialise start = 0, end = 0, to // represent the starting and ending // position of the subarray int start = 0, end = 0; // Initialise a variable sum, which // represent the sum of elements in the // current element. int sum = 0; // Initialise a variable result to // keep track of answer. int result = 0; // While end is less than size of array while (end < n) { sum += arr[end]; int len = end - start + 1; // Check if current window // is not valid if (sum * len >= k) { // Until current window // is not valid while (sum * len >= k) { // Remove the calculation // of element at start // position sum -= arr[start]; start++; len--; } // Check if current window // is valid subarray if (sum * len < k) { // If true, add (end - start + 1) // into result result += end - start + 1; } end++; } // Otherwise, Include the (end - start + 1) // into result and shift the // end by 1 else { result += end - start + 1; end++; } } // Finally, return the result return result; } public static void Main() { int [] arr = { 6, 2, 1, 4, 3 }; int K = 10; // Function call Console.WriteLine(countSubarrays(arr, K)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
// Function to find the count of the subarrays function countSubarrays(arr, k) { n = arr.length; // Initialise start = 0, end = 0, to // represent the starting and ending // position of the subarray start = 0; end = 0; // Initialise a variable sum, which // represent the sum of elements in the // current element. sum = 0; // Initialise a variable result to // keep track of answer. result = 0; // While end is less than size of array while (end < n) { sum += arr[end]; length = end - start + 1; // Check if current window // is not valid if (sum * length >= k) { // Until current window // is not valid while (sum * length >= k) { // Remove the calculation // of element at start // position sum -= arr[start]; start += 1; length -= 1; } // Check if current window // is valid subarray if (sum * length < k) { // If true, add (end - start + 1) // into result result += end - start + 1; } end += 1; } // Otherwise, Include the (end - start + 1) // into result and shift the // end by 1 else { result += end - start + 1; end += 1; } } // Finally, return the result return result; } // Driver code arr = [6, 2, 1, 4, 3]; K = 10; // Function Call console.log(countSubarrays(arr, K)); // This code is contributed by Tapesh(tapeshdua420) |
6
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles: