Sum of Subarrays with Unique elements count
Given an array arr[] of length N. The task is to calculate the sum of all subarrays where each subarray value is the number of elements in the subarray that occurs exactly once.
Examples:
Input: N = 3, arr[ ] = {2, 4, 2}
Output: 8
Explanation: All possible subarrays are
- {2}: beauty is 1.
- {4}: beauty is 1.
- {2}: beauty is 1.
- {2, 4}: beauty is 2.
- {4, 2}: beauty is 2.
- {2, 4, 2}: beauty is 1.
The sum of all beauty is 1+ 1+ 1+ 2+ 2+ 1 = 8.
Input: N = 2, arr[ ] = {1, 1}
Output: 2
Explanation: All possible subarrays are
- {1}: beauty is 1.
- {1, 1}: beauty is 0 as no element occurs only once.
- {1}: beauty is 1.
The sum of all beauty is 1 + 0 + 1 = 2.
Approach: This can be solved with the following idea:
Using map, we can see index of each element and store them in map. For each element we can check using map what will be total value in count.
Below are the steps involved:
- Intialize a map with value as vector.
- Iterate in array:
- Add index as value in map where key is its value in array.
- For each element, we need to find out the count of this element in ans.
- Count number of elements on its left
- Count number of elements on its right
- Increment the count by left * right.
- Return ans.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to calculate sum of all subarrays long long calSum( int n, vector< int > arr) { // Intialize a map map< int , vector< int > > m; int i = 0; // Iterate in array while (i < n) { // if value is not present in map if (m.find(arr[i]) == m.end()) { m[arr[i]].push_back(-1); } // Add value as a key and // index as a value m[arr[i]].push_back(i); i++; } for ( auto a : m) { m[a.first].push_back(n); } // Initialize ans = 0 long long ans = 0; for ( auto a : m) { long long count = 0; int j = 1; vector< int > v = a.second; while (j < v.size() - 1) { // Count of elements on // left side int left = v[j] - v[j - 1]; // Count of elements on // right side int right = v[j + 1] - v[j]; // Count of one elements // affecting the count count += right * 1LL * left; j++; } // Add count in ans ans += count; } // Return the ans return ans; } // Driver code int main() { int n = 3; vector< int > arr = { 2, 4, 2 }; // Function call cout << calSum(n, arr); return 0; } |
Java
// Java code for the above approach import java.util.*; public class Main { // Function to calculate the sum of all subarrays public static long calSum( int n, List<Integer> arr) { // Initialize a map HashMap<Integer, List<Integer> > m = new HashMap<>(); int i = 0 ; // Iterate through the array while (i < n) { // If the value is not present in the map if (!m.containsKey(arr.get(i))) { m.put(arr.get(i), new ArrayList<>()); m.get(arr.get(i)).add(- 1 ); } // Add the value as a key and the index as a // value m.get(arr.get(i)).add(i); i++; } for (HashMap.Entry<Integer, List<Integer> > a : m.entrySet()) { a.getValue().add(n); } // Initialize ans = 0 long ans = 0 ; for (HashMap.Entry<Integer, List<Integer> > a : m.entrySet()) { long count = 0 ; int j = 1 ; List<Integer> v = a.getValue(); while (j < v.size() - 1 ) { // Count of elements on the left side int left = v.get(j) - v.get(j - 1 ); // Count of elements on the right side int right = v.get(j + 1 ) - v.get(j); // Count of one element affecting the count count += ( long )right * left; j++; } // Add count to ans ans += count; } // Return the ans return ans; } // Driver code public static void main(String[] args) { int n = 3 ; List<Integer> arr = new ArrayList<>(); arr.add( 2 ); arr.add( 4 ); arr.add( 2 ); // Function call System.out.println(calSum(n, arr)); } } // This code is contributed by Abhinav Mahajan (abhinav_m22) |
Python
# Python code for the above approach: # Function to calculate sum of all subarrays def calSum(n, arr): # Intialize a map m = {} i = 0 # Iterate in array while (i < n): # if value is not present in map if (arr[i] not in m): m[arr[i]] = [ - 1 ] # Add value as a key and # index as a value m[arr[i]].append(i) i + = 1 for a in m: m[a].append(n) # Initialize ans = 0 ans = 0 for a in m: count, j = 0 , 1 v = m[a] while (j < len (v) - 1 ): # Count of elements on # left side left = v[j] - v[j - 1 ] # Count of elements on # right side right = v[j + 1 ] - v[j] # Count of one elements # affecting the count count + = right * left j + = 1 # Add count in ans ans + = count # Return the ans return ans # Driver code def main(): n = 3 arr = [ 2 , 4 , 2 ] # Function call print (calSum(n, arr)) if __name__ = = '__main__' : main() # This code is contributed by ragul21 |
C#
using System; using System.Collections.Generic; public class GFG { // Function to calculate the sum of all subarrays public static long CalSum( int n, List< int > arr) { // Initialize a dictionary Dictionary< int , List< int >> m = new Dictionary< int , List< int >>(); int i = 0; // Iterate through the array while (i < n) { // If the value is not present in the dictionary if (!m.ContainsKey(arr[i])) { m[arr[i]] = new List< int > { -1 }; } // Add the value as a key and the index as a value m[arr[i]].Add(i); i++; } foreach (KeyValuePair< int , List< int >> entry in m) { entry.Value.Add(n); } // Initialize ans = 0 long ans = 0; foreach (KeyValuePair< int , List< int >> entry in m) { long count = 0; int j = 1; List< int > v = entry.Value; while (j < v.Count - 1) { // Count of elements on the left side int left = v[j] - v[j - 1]; // Count of elements on the right side int right = v[j + 1] - v[j]; // Count of one element affecting the count count += ( long )right * left; j++; } // Add count to ans ans += count; } // Return the ans return ans; } // Driver code public static void Main( string [] args) { int n = 3; List< int > arr = new List< int > { 2, 4, 2 }; // Function call Console.WriteLine(CalSum(n, arr)); } } |
Javascript
// Javascript code for the above approach: // Function to calculate sum of all subarrays function calSum(n, arr) { // Intialize a map const m = new Map(); let i = 0; // Iterate in array while (i < n) { // if value is not present in map if (!m.has(arr[i])) { m.set(arr[i], [-1]); } // Add value as a key and // index as a value m.get(arr[i]).push(i); i++; } for (const [key, value] of m) { value.push(n); } // Initialize ans = 0 let ans = 0; for (const [key, value] of m) { let count = 0; let j = 1; const v = value; while (j < v.length - 1) { // Count of elements on // left side const left = v[j] - v[j - 1]; // Count of elements on // right side const right = v[j + 1] - v[j]; // Count of one elements // affecting the count count += right * left; j++; } // Add count in ans ans += count; } // Return the ans return ans; } // Driver code const n = 3; const arr = [2, 4, 2]; // Function call console.log(calSum(n, arr)); // This code is contributed by ragul21 |
Output
8
Time Complexity: O(n*log n)
Auxiliary Space: O(n)