Given an array of n elements and an integer X. Count the number of sub-arrays of this array which have all elements less than or equal to X.
Examples:
Input : arr[] = {1, 5, 7, 8, 2, 3, 9}
X = 6
Output : 6
Explanation : Sub-arrays are {1}, {5}, {2}, {3},
{1, 5}, {2, 3}
Input : arr[] = {1, 10, 12, 4, 5, 3, 2, 7}
X = 9
Output : 16
Naive Approach : A simple approach uses two nested loops for generating all sub-arrays of the given an array and a loop to check whether all elements of a sub-array is less than or equal to X or not.
Time Complexity: O(n*n*n)
Efficient Approach: An efficient approach is to observe that we just want the count of those sub-arrays which have all elements less than or equal to X. We can create a binary array of 0s and 1s corresponding to the original array. If an element in the original is less than or equal to X, then the corresponding element in the binary array will be 1 otherwise 0. Now, our problem reduces to count the number of sub-arrays in this binary array which has all 1s. We can also see that for an array which has all 1s all of its sub-arrays will have only 1s and the total number of sub-arrays will be len*(len+1)/2. For example, {1, 1, 1, 1} will have 10 sub-arrays.
Below is the complete algorithm to solve the above problem:
- Create a corresponding binary array of the original array as described above.
- Initialize a counter variable to 0 and start traversing the binary array keeping track of the lengths of sub-arrays which has all 1s
- We can easily calculate the number of sub-arrays of an array which has all 1s by using the formula n*(n+1)/2, where n is the length of the array with all 1s.
- Calculate the length of every sub-array which has all 1s and increment the count variable by length*(length+1)/2. We can do this in O(n) time complexity
Below is the implementation of above approach:
C++
// C++ program to count all sub-arrays which// has all elements less than or equal to X#include <iostream>using namespace std;// function to count all sub-arrays which// has all elements less than or equal to Xint countSubArrays(int arr[], int n, int x){ // variable to keep track of length of // subarrays with all 1s int len = 0; // variable to keep track of all subarrays int count = 0; // binary array of same size int binaryArr[n]; // creating binary array for (int i = 0; i < n; i++) { if (arr[i] <= x) binaryArr[i] = 1; else binaryArr[i] = 0; } // start traversing the binary array for (int i = 0; i < n; i++) { // once we find the first 1, keep checking // for number of consecutive 1s if (binaryArr[i] == 1) { int j; for (j = i + 1; j < n; j++) if (binaryArr[j] != 1) break; // calculate length of the subarray // with all 1s len = j - i; // increment count count += (len) * (len + 1) / 2; // initialize i to j i = j; } } return count;}// Driver codeint main(){ int arr[] = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; int n = sizeof(arr) / sizeof(arr[0]); cout << countSubArrays(arr, n, x); return 0;} |
Java
// Java program to count all sub-arrays which// has all elements less than or equal to Ximport java.io.*;class GFG { // function to count all sub-arrays which // has all elements less than or equal to X static int countSubArrays(int arr[], int n, int x) { // variable to keep track of length of // subarrays with all 1s int len = 0; // variable to keep track of all subarrays int count = 0; // binary array of same size int binaryArr[] = new int[n]; // creating binary array for (int i = 0; i < n; i++) { if (arr[i] <= x) binaryArr[i] = 1; else binaryArr[i] = 0; } // start traversing the binary array for (int i = 0; i < n; i++) { // once we find the first 1, keep checking // for number of consecutive 1s if (binaryArr[i] == 1) { int j; for (j = i + 1; j < n; j++) if (binaryArr[j] != 1) break; // calculate length of the subarray // with all 1s len = j - i; // increment count count += (len) * (len + 1) / 2; // initialize i to j i = j; } } return count; } // Driver code public static void main(String args[]) { int arr[] = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; int n = arr.length; System.out.println(countSubArrays(arr, n, x)); }}// This code is contributed by Nikita Tiwari. |
Python3
# python 3 program to count all sub-arrays which# has all elements less than or equal to X# function to count all sub-arrays which# has all elements less than or equal to Xdef countSubArrays(arr, n, x): # variable to keep track of length # of subarrays with all 1s len = 0 # variable to keep track of # all subarrays count = 0 # binary array of same size binaryArr = [0 for i in range(n)] # creating binary array for i in range(0, n, 1): if (arr[i] <= x): binaryArr[i] = 1 else: binaryArr[i] = 0 # start traversing the binary array for i in range(0, n, 1): # once we find the first 1, # keep checking for number # of consecutive 1s if (binaryArr[i] == 1): for j in range(i + 1, n, 1): if (binaryArr[j] != 1): break # calculate length of the # subarray with all 1s len = j - i # increment count count += (len) * (int)((len + 1) / 2) # initialize i to j i = j return count# Driver codeif __name__ == '__main__': arr = [1, 5, 7, 8, 2, 3, 9] x = 6 n = len(arr) print(int(countSubArrays(arr, n, x))) # This code is contributed by# Surendra_Gangwar |
C#
// C# program to count all sub-arrays which// has all elements less than or equal to X1using System;class GFG { // function to count all sub-arrays which // has all elements less than or equal // to X static int countSubArrays(int []arr, int n, int x) { // variable to keep track of length // of subarrays with all 1s int len = 0; // variable to keep track of all // subarrays int count = 0; // binary array of same size int []binaryArr = new int[n]; // creating binary array for (int i = 0; i < n; i++) { if (arr[i] <= x) binaryArr[i] = 1; else binaryArr[i] = 0; } // start traversing the binary array for (int i = 0; i < n; i++) { // once we find the first 1, keep // checking for number of // consecutive 1s if (binaryArr[i] == 1) { int j; for (j = i + 1; j< n; j++) if (binaryArr[j] != 1) break; // calculate length of the // subarray with all 1s len = j - i; // increment count count += (len) * (len + 1) / 2; // initialize i to j i = j; } } return count; } // Driver code public static void Main() { int []arr = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; int n = arr.Length; Console.WriteLine( countSubArrays(arr, n, x)); }}// This code is contributed by Sam007. |
PHP
<?php// PHP program to count all sub-arrays which// has all elements less than or equal to X// function to count all sub-arrays which// has all elements less than or equal to Xfunction countSubArrays($arr, $n, $x){ // variable to keep track of length of // subarrays with all 1s $len = 0; // variable to keep track of all subarrays $coun = 0; // binary array of same size $binaryArr = array($n); // creating binary array for ($i = 0; $i < $n; $i++) { if ($arr[$i] <= $x) $binaryArr[$i] = 1; else $binaryArr[$i] = 0; } // start traversing // the binary array for ($i = 0; $i < $n; $i++) { // once we find the first 1, // keep checking for number // of consecutive 1s if ($binaryArr[$i] == 1) { for ($j = $i + 1; $j < $n; $j++) if ($binaryArr[$j] != 1) break; // calculate length of // the subarray with all 1s $len = $j - $i; // increment count $coun += ($len) * ($len + 1) / 2; // initialize i to j $i = $j; } } return $coun;} // Driver code $arr = array( 1, 5, 7, 8, 2, 3, 9 ); $x = 6; $n = count($arr); echo countSubArrays($arr, $n, $x);// This code is contributed by Sam007?> |
Javascript
<script>// javascript program to count all sub-arrays which// has all elements less than or equal to X // function to count all sub-arrays which // has all elements less than or equal to X function countSubArrays(arr , n , x) { // variable to keep track of length of // subarrays with all 1s var len = 0; // variable to keep track of all subarrays var count = 0; // binary array of same size var binaryArr = Array(n).fill(0); // creating binary array for (i = 0; i < n; i++) { if (arr[i] <= x) binaryArr[i] = 1; else binaryArr[i] = 0; } // start traversing the binary array for (i = 0; i < n; i++) { // once we find the first 1, keep checking // for number of consecutive 1s if (binaryArr[i] == 1) { var j; for (j = i + 1; j < n; j++) if (binaryArr[j] != 1) break; // calculate length of the subarray // with all 1s len = j - i; // increment count count += (len) * (len + 1) / 2; // initialize i to j i = j; } } return count; } // Driver code var arr = [ 1, 5, 7, 8, 2, 3, 9 ]; var x = 6; var n = arr.length; document.write(countSubArrays(arr, n, x));// This code is contributed by Rajput-Ji</script> |
Output:
6
Time Complexity: O(n), where n is the number of elements in the array.
Auxiliary Space: O(n).
Another Method: We can improve the above solution without using extra space keeping the time complexity O(n). Instead of marking elements as 0 and 1 we can keep track of start and end of each such region and update the count whenever the region ends.
Implementation:
C++
// C++ program to count all sub-arrays which// has all elements less than or equal to X#include<bits/stdc++.h>using namespace std;int countSubArrays(int arr[], int x, int n ) { int count = 0; int start = -1, end = -1; for(int i = 0; i < n; i++) { if(arr[i] < x) { if(start == -1) { //create a new subArray start = i; end = i; } else { // append to existing subarray end=i; } } else { if(start != -1 && end != -1) { // given start and end calculate // all subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } start = -1; end = -1; } } if(start != -1 && end != -1) { // given start and end calculate all // subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } return count; } // Driver code int main() { int arr[] = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; int n = sizeof(arr) / sizeof(arr[0]); cout<< countSubArrays(arr, x, n); //This code is contributed by 29AjayKumar } |
Java
// Java program to count all sub-arrays which// has all elements less than or equal to Xpublic class GFG { public static int countSubArrays(int arr[], int x) { int count = 0; int start = -1, end = -1; for(int i = 0; i < arr.length; i++) { if(arr[i] < x) { if(start == -1) { //create a new subArray start = i; end = i; } else { // append to existing subarray end=i; } } else { if(start != -1 && end != -1) { // given start and end calculate // all subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } start = -1; end = -1; } } if(start != -1 && end != -1) { // given start and end calculate all // subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } return count; } // Driver code public static void main(String[] args) { int arr[] = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; System.out.println(countSubArrays(arr, x)); }} |
Python3
# Python3 program to count all sub-arrays which# has all elements less than or equal to Xdef countSubArrays(arr, x, n ): count = 0; start = -1; end = -1; for i in range(n): if(arr[i] < x): if(start == -1): # create a new subArray start = i; end = i; else: # append to existing subarray end = i; else: if(start != -1 and end != -1): # given start and end calculate # all subarrays within this range length = end - start + 1; count = count + ((length * (length + 1)) / 2); start = -1; end = -1; if(start != -1 and end != -1): # given start and end calculate all # subarrays within this range length = end - start + 1; count = count + ((length * (length + 1)) / 2); return count;# Driver code arr = [ 1, 5, 7, 8, 2, 3, 9 ];x = 6;n = len(arr);print(countSubArrays(arr, x, n));# This code is contributed # by PrinciRaj1992 |
C#
// C# program to count all sub-arrays which// has all elements less than or equal to Xusing System;class GFG { public static int countSubArrays(int []arr, int x) { int count = 0; int start = -1, end = -1; for(int i = 0; i < arr.Length; i++) { if(arr[i] < x) { if(start == -1) { //create a new subArray start = i; end = i; } else { // append to existing subarray end=i; } } else { if(start != -1 && end != -1) { // given start and end calculate // all subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } start = -1; end = -1; } } if(start != -1 && end != -1) { // given start and end calculate all // subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } return count; } // Driver code public static void Main(String[] args) { int []arr = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; Console.WriteLine(countSubArrays(arr, x)); }}// This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program to count all sub-arrays which // has all elements less than or equal to X function countSubArrays(arr, x) { let count = 0; let start = -1, end = -1; for(let i = 0; i < arr.length; i++) { if(arr[i] < x) { if(start == -1) { //create a new subArray start = i; end = i; } else { // append to existing subarray end=i; } } else { if(start != -1 && end != -1) { // given start and end calculate // all subarrays within this range let length = end - start + 1; count = count + parseInt((length * (length + 1)) / 2, 10); } start = -1; end = -1; } } if(start != -1 && end != -1) { // given start and end calculate all // subarrays within this range let length = end - start + 1; count = count + parseInt((length * (length + 1)) / 2, 10); } return count; } let arr = [ 1, 5, 7, 8, 2, 3, 9 ]; let x = 6; document.write(countSubArrays(arr, x)); </script> |
Output:
6
Time Complexity: O(n), where n is the number of elements in the array.
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
