Given an array arr[] of size N, the task is to count the number of subarrays consisting of a single distinct element that can be obtained from a given array.
Examples:
Input: N = 4, arr[] = { 2, 2, 2, 2 }
Output: 7
Explanation: All such subarrays {{2}, {2}, {2}, {2}, {2, 2}, {2, 2, 2}, {2, 2, 2, 2}}. Therefore, total count of such subarrays are 7.Input: N = 3, arr[] = { 1, 1, 3 }
Output: 4
Approach: Follow the steps below to solve the problem:
- Initialize a Map to store the frequency of array elements.
- Traverse the array and update frequency of each element in the Map.
- Traverse the Map and check if frequency of current element is greater than 1.
- If found to be true, then increment count of subarrays by frequency of current element – 1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count subarrays of// single distinct element into// which given array can be splitvoid divisionalArrays(int arr[3], int N){ // Stores the count int sum = N; // Stores frequency of // array elements unordered_map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) { mp[arr[i]]++; } // Traverse the map for (auto x : mp) { if (x.second > 1) { // Increase count of // subarrays by (frequency-1) sum += x.second - 1; } } cout << sum << endl;}// Driver Codeint main(){ int arr[] = { 1, 1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); divisionalArrays(arr, N);} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to count subarrays of // single distinct element into // which given array can be split static void divisionalArrays(int arr[], int N) { // Stores the count int sum = N; // Stores frequency of // array elements HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse the array for (int i = 0; i < N; i++) { if (mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1); } else { mp.put(arr[i], 1); } } // Traverse the map for (Map.Entry x : mp.entrySet()) { if ((int)x.getValue() > 1) { // Increase count of // subarrays by (frequency-1) sum += (int)x.getValue() - 1; } } System.out.println(sum); } // Driver Code public static void main(String[] args) { int arr[] = { 1, 1, 3 }; int N = arr.length; divisionalArrays(arr, N); }}// This code is contributed by Dharanendra L V |
Python3
# python 3 program for the above approachfrom collections import defaultdict# Function to count subarrays of# single distinct element into# which given array can be splitdef divisionalArrays(arr, N): # Stores the count sum = N # Stores frequency of # array elements mp = defaultdict(int) # Traverse the array for i in range(N): mp[arr[i]] += 1 # Traverse the map for x in mp: if (mp[x] > 1): # Increase count of # subarrays by (frequency-1) sum += mp[x] - 1 print(sum)# Driver Codeif __name__ == "__main__": arr = [1, 1, 3] N = len(arr) divisionalArrays(arr, N) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count subarrays of// single distinct element into// which given array can be splitstatic void divisionalArrays(int []arr, int N){ // Stores the count int sum = N; // Stores frequency of // array elements Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for (int i = 0; i < N; i++) { if (mp.ContainsKey(arr[i])) { mp[arr[i]] = mp[arr[i]] + 1; } else { mp.Add(arr[i], 1); } } // Traverse the map foreach(KeyValuePair<int, int> x in mp) { if ((int)x.Value > 1) { // Increase count of // subarrays by (frequency-1) sum += (int)x.Value - 1; } } Console.WriteLine(sum);}// Driver Codepublic static void Main(String[] args){ int []arr = { 1, 1, 3 }; int N = arr.Length; divisionalArrays(arr, N);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach// Function to count subarrays of// single distinct element into// which given array can be splitfunction divisionalArrays(arr, N){ // Stores the count var sum = N; // Stores frequency of // array elements var mp = new Map(); // Traverse the array for (var i = 0; i < N; i++) { if(mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i])+1); } else { mp.set(arr[i],1); } } // Traverse the map mp.forEach((value, key) => { if (value > 1) { // Increase count of // subarrays by (frequency-1) sum += value - 1; } }); document.write( sum);}// Driver Codevar arr =[1, 1, 3];var N = arr.length;divisionalArrays(arr, N);</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
