Given an array A of size N where the array elements contain values from 1 to N with duplicates, the task is to find the total number of subarrays that start and end with the same element.
Examples:
Input: A[] = {1, 2, 1, 5, 2}
Output: 7
Explanation:
Total 7 sub-array of the given array are {1}, {2}, {1}, {5}, {2}, {1, 2, 1} and {2, 1, 5, 2} are start and end with same element.
Input: A[] = {1, 5, 6, 1, 9, 5, 8, 10, 8, 9}
Output: 14
Explanation:
Total 14 sub-array {1}, {5}, {6}, {1}, {9}, {5}, {8}, {10}, {8}, {9}, {1, 5, 6, 1}, {5, 6, 1, 9, 5}, {9, 5, 8, 10, 8, 9} and {8, 10, 8} start and end with same element.
Naive approach: For each element in the array, if it is present at a different index as well, we will increase our result by 1. Also, all 1-size subarray are part of counted in the result. Therefore, add N to the result.
Below is the implementation of the above approach:
C++
// C++ program to Count total sub-array // which start and end with same element #include <bits/stdc++.h> using namespace std; // Function to find total sub-array // which start and end with same element void cntArray(int A[], int N) { // initialize result with 0 int result = 0; for (int i = 0; i < N; i++) { // all size 1 sub-array // is part of our result result++; // element at current index int current_value = A[i]; for (int j = i + 1; j < N; j++) { // Check if A[j] = A[i] // increase result by 1 if (A[j] == current_value) { result++; } } } // print the result cout << result << endl; } // Driver code int main() { int A[] = { 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 }; int N = sizeof(A) / sizeof(int); cntArray(A, N); return 0; } |
Java
// Java program to Count total sub-array // which start and end with same element public class Main { // function to find total sub-array // which start and end with same element public static void cntArray(int A[], int N) { // initialize result with 0 int result = 0; for (int i = 0; i < N; i++) { // all size 1 sub-array // is part of our result result++; // element at current index int current_value = A[i]; for (int j = i + 1; j < N; j++) { // Check if A[j] = A[i] // increase result by 1 if (A[j] == current_value) { result++; } } } // print the result System.out.println(result); } // Driver code public static void main(String[] args) { int[] A = { 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 }; int N = A.length; cntArray(A, N); } } |
Python3
# Python3 program to count total sub-array # which start and end with same element # Function to find total sub-array # which start and end with same element def cntArray(A, N): # Initialize result with 0 result = 0 for i in range(0, N): # All size 1 sub-array # is part of our result result = result + 1 # Element at current index current_value = A[i] for j in range(i + 1, N): # Check if A[j] = A[i] # increase result by 1 if (A[j] == current_value): result = result + 1 # Print the result print(result) print("\n") # Driver code A = [ 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 ] N = len(A) cntArray(A, N) # This code is contributed by PratikBasu |
C#
// C# program to Count total sub-array // which start and end with same element using System; class GFG{ // function to find total sub-array // which start and end with same element public static void cntArray(int []A, int N) { // initialize result with 0 int result = 0; for (int i = 0; i < N; i++) { // all size 1 sub-array // is part of our result result++; // element at current index int current_value = A[i]; for (int j = i + 1; j < N; j++) { // Check if A[j] = A[i] // increase result by 1 if (A[j] == current_value) { result++; } } } // print the result Console.Write(result); } // Driver code public static void Main() { int[] A = { 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 }; int N = A.Length; cntArray(A, N); } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript program to Count total sub-array // which start and end with same element // Function to find total sub-array // which start and end with same element function cntArray(A, N) { // initialize result with 0 var result = 0; for (var i = 0; i < N; i++) { // all size 1 sub-array // is part of our result result++; // element at current index var current_value = A[i]; for (var j = i + 1; j < N; j++) { // Check if A[j] = A[i] // increase result by 1 if (A[j] == current_value) { result++; } } } // print the result document.write( result ); } // Driver code var A = [1, 5, 6, 1, 9, 5, 8, 10, 8, 9]; var N = A.length; cntArray(A, N); // This code is contributed by noob2000. </script> |
Output:
14
Time Complexity: O(N2), where N is the size of the array
Space complexity: O(1)
Efficient approach: We can optimize the above method by observing that the answer just depends on frequencies of numbers in the original array.
For example in array {1, 5, 6, 1, 9, 5, 8, 10, 8, 9}, frequency of 1 is 2 and sub-array contributing to answer are {1}, {1} and {1, 5, 6, 1} respectively, i.e., a total of 3.
Therefore, calculate the frequency of each element in the array. Then for each element, the increment the count by the result yielded by the following formula:
((frequency of element)*(frequency of element + 1)) / 2
Below is the implementation of the above approach:
C++
// C++ program to Count total sub-array // which start and end with same element #include <bits/stdc++.h> using namespace std; // function to find total sub-array // which start and end with same element void cntArray(int A[], int N) { // initialize result with 0 int result = 0; // array to count frequency of 1 to N int frequency[N + 1] = { 0 }; for (int i = 0; i < N; i++) { // update frequency of A[i] frequency[A[i]]++; } for (int i = 1; i <= N; i++) { int frequency_of_i = frequency[i]; // update result with sub-array // contributed by number i result += +((frequency_of_i) * (frequency_of_i + 1)) / 2; } // print the result cout << result << endl; } // Driver code int main() { int A[] = { 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 }; int N = sizeof(A) / sizeof(int); cntArray(A, N); return 0; } |
Java
// Java program to Count total sub-array // which start and end with same element public class Main { // function to find total sub-array which // start and end with same element public static void cntArray(int A[], int N) { // initialize result with 0 int result = 0; // array to count frequency of 1 to N int[] frequency = new int[N + 1]; for (int i = 0; i < N; i++) { // update frequency of A[i] frequency[A[i]]++; } for (int i = 1; i <= N; i++) { int frequency_of_i = frequency[i]; // update result with sub-array // contributed by number i result += ((frequency_of_i) * (frequency_of_i + 1)) / 2; } // print the result System.out.println(result); } // Driver code public static void main(String[] args) { int[] A = { 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 }; int N = A.length; cntArray(A, N); } } |
Python3
# Python3 program to count total sub-array # which start and end with same element # Function to find total sub-array # which start and end with same element def cntArray(A, N): # Initialize result with 0 result = 0 # Array to count frequency of 1 to N frequency = [0] * (N + 1) for i in range(0, N): # Update frequency of A[i] frequency[A[i]] = frequency[A[i]] + 1 for i in range(1, N + 1): frequency_of_i = frequency[i] # Update result with sub-array # contributed by number i result = result + ((frequency_of_i) * (frequency_of_i + 1)) / 2 # Print the result print(int(result)) print("\n") # Driver code A = [ 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 ] N = len(A) cntArray(A, N) # This code is contributed by PratikBasu |
C#
// C# program to Count total sub-array // which start and end with same element using System; class GFG{ // function to find total sub-array which // start and end with same element public static void cntArray(int []A, int N) { // initialize result with 0 int result = 0; // array to count frequency of 1 to N int[] frequency = new int[N + 1]; for (int i = 0; i < N; i++) { // update frequency of A[i] frequency[A[i]]++; } for (int i = 1; i <= N; i++) { int frequency_of_i = frequency[i]; // update result with sub-array // contributed by number i result += ((frequency_of_i) * (frequency_of_i + 1)) / 2; } // print the result Console.Write(result); } // Driver code public static void Main() { int[] A = { 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 }; int N = A.Length; cntArray(A, N); } } // This code is contributed by Nidhi_Biet |
Javascript
<script> // Javascript program to Count total sub-array // which start and end with same element // function to find total sub-array which // start and end with same element function cntArray(A, N) { // initialize result with 0 let result = 0; // array to count frequency of 1 to N let frequency = Array.from({length: N+1}, (_, i) => 0); for (let i = 0; i < N; i++) { // update frequency of A[i] frequency[A[i]]++; } for (let i = 1; i <= N; i++) { let frequency_of_i = frequency[i]; // update result with sub-array // contributed by number i result += ((frequency_of_i) * (frequency_of_i + 1)) / 2; } // print the result document.write(result); } // Driver Code let A = [ 1, 5, 6, 1, 9, 5, 8, 10, 8, 9 ]; let N = A.length; cntArray(A, N); </script> |
Output:
14
Time Complexity: O(N), where N is the size of the array
Space complexity: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
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!
