Given an array A[] of length N, the task is to count the number of subarrays of A[] that contain the length of that subarray.
Examples:
Input: A = {10, 11, 1}, N = 3
Output: 1
Explanation: Only the subarray {1}, with a length 1, contains its own length.Input: A = [1, 2, 3, 4, 5], N = 5
Output: 9
Explanation: The subarrays {1}, {1, 2}, {2, 3}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5},
{1, 2, 3, 4}, {2, 3, 4, 5}, {1, 2, 3, 4, 5} contain their own length.
Approach: Follow the below idea to solve the problem:
First, form each and every subarray of A. Then, check if the length of the subarray is present in that subarray.
Follow the steps mentioned below to implement the idea:
- Iterate over the array from i = 0 to N:
- Iterate in a nested loop from j = i to N:
- The subarray created is from i to j.
- Traverse the subarray and check if the length is present in the subarray.
- If present, then increment the count.
- The final count is the required answer.
Below is the implementation for the above approach:
C++
// C++ code to implement the approach #include <iostream> using namespace std; // Function to find the count of the subarrays // that contain their own length int findCount( int arr[], int N) { int counts = 0; // Forming all possible subarrays for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N + 1; j++) { // Checking if the length is present // in the subarray for ( int k = i; k <= j; k++) { if ((j - i) == arr[k]) counts += 1; } } } return counts; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int N = 5; // Function Call cout << findCount(arr, N); return 0; } // This code is contributed by Rohit Pradhan |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the count of the subarrays // that contain their own length static int findCount( int [] arr, int N) { int counts = 0 ; // Forming all possible subarrays for ( int i = 0 ; i < N; i++) { for ( int j = i + 1 ; j < N + 1 ; j++) { // Checking if the length is present // in the subarray for ( int k = i; k <= j; k++) { if ((j - i) == arr[k]) counts += 1 ; } } } return counts; } // Driver Code public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int N = 5 ; // Function Call System.out.println( findCount(arr, N)); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python3 code to implement the approach # Function to find the count of the subarrays # that contain their own length def findCount(arr, N): counts = 0 # Forming all possible subarrays for i in range (N): for j in range (i + 1 , N + 1 ): # Checking if the length is present # in the subarray if j - i in arr[i: j]: counts + = 1 return counts # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 4 , 5 ] N = 5 # Function Call print (findCount(arr, N)) |
C#
// C# code to implement the above approach using System; public class GFG { // Function to find the count of the subarrays // that contain their own length static int findCount( int [] arr, int N) { int counts = 0; // Forming all possible subarrays for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N + 1; j++) { // Checking if the length is present // in the subarray for ( int k = i; k < j; k++) { if ((j - i) == arr[k]) counts += 1; } } } return counts; } // Driver Code public static void Main ( string [] args) { int []arr = { 1, 2, 3, 4, 5 }; int N = 5; // Function Call Console.WriteLine(findCount(arr, N)); } } // This code is contributed by AnkThon |
Javascript
<script> // JavaScript code for the above approach // Function to find the count of the subarrays // that contain their own length function findCount(arr, N) { let counts = 0 // Forming all possible subarrays for (let i = 0; i < N; i++) { for (let j = i + 1; j < N + 1; j++) { // Checking if the length is present // in the subarray for (let k = i; k <= j; k++) { if (arr[k] == j - i) { counts++; } } } } return counts } // Driver Code let arr = [1, 2, 3, 4, 5] let N = 5 // Function Call document.write(findCount(arr, N)) // This code is contributed by Potta Lokesh </script> |
9
Time complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach:-
- As the previous approach running in O(N^3) time
- We can optimize the 3rd for loop of that approach by observing that we are finding length only in that loop but if we use hashmap to store element for each subarray then we can find the length in O(1) time
- So in this approach we will be using hashmap to store elements and then find the length of subarray present or not
Implementation:-
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the count of the subarrays // that contain their own length int findCount( int arr[], int N) { int counts = 0; // Forming all possible subarrays for ( int i = 0; i < N; i++) { //map to store frequency unordered_map< int , int > mm; for ( int j = i; j < N; j++) { mm[arr[j]]++; //finding length is present or not if (mm[j-i+1])counts++; } } return counts; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int N = 5; // Function Call cout << findCount(arr, N); return 0; } // This code is contributed by shubhamrajput6156 |
Java
// Java code to implement the approach import java.util.*; public class Main { // Function to find the count of the subarrays // that contain their own length public static int findCount( int [] arr, int N) { int counts = 0 ; // Forming all possible subarrays for ( int i = 0 ; i < N; i++) { // Map to store frequency Map<Integer, Integer> mm = new HashMap<>(); for ( int j = i; j < N; j++) { if (mm.containsKey(arr[j])) { mm.put(arr[j], mm.get(arr[j]) + 1 ); } else { mm.put(arr[j], 1 ); } // finding length is present or not if (mm.get(j-i+ 1 ) != null && mm.get(j-i+ 1 ) > 0 ) { counts++; } } } return counts; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 }; int N = 5 ; // Function Call System.out.println(findCount(arr, N)); } } |
Python3
# Python code to implement the approach # Function to find the count of the subarrays # that contain their own length def find_count(arr, N): counts = 0 # Forming all possible subarrays for i in range (N): # dict to store frequency mm = {} for j in range (i, N): if arr[j] in mm: mm[arr[j]] + = 1 else : mm[arr[j]] = 1 # finding length is present or not if mm.get(j - i + 1 , 0 ): counts + = 1 return counts # Driver Code arr = [ 1 , 2 , 3 , 4 , 5 ] N = 5 # Function Call print (find_count(arr, N)) |
C#
//C# equivalent code using System; using System.Collections.Generic; public class Program { // Function to find the count of the subarrays // that contain their own length public static int findCount( int [] arr, int N) { int counts = 0; // Forming all possible subarrays for ( int i = 0; i < N; i++) { // Dictionary to store frequency Dictionary< int , int > mm = new Dictionary< int , int >(); for ( int j = i; j < N; j++) { if (mm.ContainsKey(arr[j])) { mm[arr[j]] = mm[arr[j]] + 1; } else { mm.Add(arr[j], 1); } // finding length is present or not if (mm.ContainsKey(j - i + 1) && mm[j - i + 1] > 0) { counts++; } } } return counts; } // Driver Code public static void Main( string [] args) { int [] arr = { 1, 2, 3, 4, 5 }; int N = 5; // Function Call Console.WriteLine(findCount(arr, N)); } } |
Javascript
function findCount(arr, N) { let counts = 0; // Forming all possible subarrays for (let i = 0; i < N; i++) { // object to store frequency let mm = {}; for (let j = i; j < N; j++) { if (mm[arr[j]]) { mm[arr[j]] += 1; } else { mm[arr[j]] = 1; } // finding length is present or not if (mm[j - i + 1]) { counts += 1; } } } return counts; } // Driver Code let arr = [1, 2, 3, 4, 5]; let N = 5; // Function Call console.log(findCount(arr, N)); |
9
Time Complexity:- O(N^2)
Auxiliary Space:- O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!