Count of Subarrays which Contain the Length of that Subarray

0 0 6 minutes read

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>

Output

Time complexity: O(N³)
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));

Output

Time Complexity:- O(N^2)
Auxiliary Space:- O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!