Find sum of count of duplicate numbers in all subarrays of given array
Given an array arr[] of size N. The task it to find the sum of count of duplicate numbers in all subarrays of given array arr[]. For example array {1, 2, 3, 2, 3, 2} has two duplicate elements (i.e, 2 and 3 come more than one time in the array).
Examples:
Input: N = 2, arr = {3,3}
Output: 1
Explanation: All subarrays of the arr are {3}, {3,3}, {3} have values 0, 1, 0 respectively, so the answer is 1.Input: N = 4, arr = {1, 2, 1, 2}
Output: 4
Explanation: All subarrays of the arr are {1},{1,2},{1,2,1},{1,2,1,2},{2},{2,1},{2,1,2},{1},{1,2},{2} have values 0,0,1,2,0,0,1,0,0,0 respectively, so answer is 4.
Approach: This can be solved with the following idea:
To avoid considering all possible subarrays, we can use below approach:
We can first create a map that stores the positions of each distinct element in the array. Then, for each distinct element, we calculate the contribution of subarrays that contain this element. This avoids the need to iterate through all subarrays explicitly.
Step-by-step approach:
- Initialize an unordered map mp of arrays m to store all positions of each distinct element in the array.
- Iterate through the array arr and populate the map. For each element, append its position to the corresponding entry in the map.
- Initialize a variable ans for answer.
- Iterate through the entries in the mp:
- If an element appears only once, continue to the next element as there can be no subarray with distinct elements that appear more than once.
- For elements that appear more than once, calculate their contribution to the count of subarrays:
- Initialize a variable prev to -1 to represent the position before the first occurrence of the element.
- Iterate through the positions of the element and calculate the contribution of subarrays containing this element. The contribution is determined by the product of the distance to the previous occurrence of the element and the distance to the next occurrence.
- Update ans with the calculated contribution, taking the modulo operation to avoid integer overflow.
- Update prev to the current position.
- Return the final value of ans.
Below is the implementation of the above approach:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find the values of subarrays int ValueOfSubarrays( int N, vector< int >& arr) { int i = 0; // Initailze a map unordered_map< int , vector< int > > mp; // Iterate in array while (i < arr.size()) { mp[arr[i]].push_back(i); i++; } i = 0; int mod = 1e9 + 7; long long prev = -1; long long ans = 0; // Interate in map for ( auto a : mp) { prev = -1; // I frequency is 1 if (a.second.size() == 1) { continue ; } int j = 0; // Iterate to find the impact of each element while (j < a.second.size() - 1) { ans += (a.second[j] - prev) * (N - a.second[j + 1]); ans %= mod; prev = a.second[j]; j++; } } // Return the value return ans; } // Driver code int main() { int N = 5; vector< int > arr = { 1, 2, 2, 3, 2 }; // Function call cout << ValueOfSubarrays(N, arr); return 0; } |
Java
import java.util.*; public class SubarraysValue { // Function to find the values of subarrays static int valueOfSubarrays( int N, ArrayList<Integer> arr) { int i = 0 ; // Initialize a map HashMap<Integer, ArrayList<Integer>> mp = new HashMap<>(); // Iterate in array while (i < arr.size()) { if (!mp.containsKey(arr.get(i))) { mp.put(arr.get(i), new ArrayList<>()); } mp.get(arr.get(i)).add(i); i++; } i = 0 ; int mod = ( int ) 1e9 + 7 ; long prev = - 1 ; long ans = 0 ; // Iterate in map for (Map.Entry<Integer, ArrayList<Integer>> entry : mp.entrySet()) { prev = - 1 ; // If frequency is 1 if (entry.getValue().size() == 1 ) { continue ; } int j = 0 ; // Iterate to find the impact of each element while (j < entry.getValue().size() - 1 ) { ans += (entry.getValue().get(j) - prev) * (N - entry.getValue().get(j + 1 )); ans %= mod; prev = entry.getValue().get(j); j++; } } // Return the value return ( int ) ans; } // Driver code public static void main(String[] args) { int N = 5 ; ArrayList<Integer> arr = new ArrayList<>(Arrays.asList( 1 , 2 , 2 , 3 , 2 )); // Function call System.out.println(valueOfSubarrays(N, arr)); } } |
Python3
def value_of_subarrays(N, arr): # Initialize a dictionary to store indices of each element mp = {} # Iterate in array i = 0 while i < len (arr): if arr[i] not in mp: mp[arr[i]] = [] mp[arr[i]].append(i) i + = 1 i = 0 mod = 10 * * 9 + 7 prev = - 1 ans = 0 # Iterate in the dictionary for key, value in mp.items(): prev = - 1 # If frequency is 1, no impact on subarrays if len (value) = = 1 : continue j = 0 # Iterate to find the impact of each element while j < len (value) - 1 : ans + = (value[j] - prev) * (N - value[j + 1 ]) ans % = mod prev = value[j] j + = 1 # Return the value return ans # Driver code if __name__ = = "__main__" : N = 5 arr = [ 1 , 2 , 2 , 3 , 2 ] # Function call print (value_of_subarrays(N, arr)) |
C#
using System; using System.Collections.Generic; public class SubarraysValue { // Function to find the values of subarrays static int ValueOfSubarrays( int N, List< int > arr) { int i = 0; // Initialize a dictionary Dictionary< int , List< int >> mp = new Dictionary< int , List< int >>(); // Iterate in array while (i < arr.Count) { if (!mp.ContainsKey(arr[i])) { mp[arr[i]] = new List< int >(); } mp[arr[i]].Add(i); i++; } i = 0; int mod = ( int )1e9 + 7; long prev = -1; long ans = 0; // Iterate in dictionary foreach ( var a in mp) { prev = -1; // If frequency is 1 if (a.Value.Count == 1) { continue ; } int j = 0; // Iterate to find the impact of each element while (j < a.Value.Count - 1) { ans += (a.Value[j] - prev) * (N - a.Value[j + 1]); ans %= mod; prev = a.Value[j]; j++; } } // Return the value return ( int )ans; } // Driver code public static void Main() { int N = 5; List< int > arr = new List< int > { 1, 2, 2, 3, 2 }; // Function call Console.WriteLine(ValueOfSubarrays(N, arr)); } } //this code is contributed by Aman |
Javascript
function valueOfSubarrays(N, arr) { // Initialize a Map to store indices of each element let mp = new Map(); // Iterate in array for (let i = 0; i < arr.length; i++) { if (!mp.has(arr[i])) { mp.set(arr[i], []); } mp.get(arr[i]).push(i); } let mod = 10**9 + 7; let prev = -1; let ans = 0; // Iterate in the Map for (let [key, value] of mp) { prev = -1; // If frequency is 1, no impact on subarrays if (value.length === 1) { continue ; } let j = 0; // Iterate to find the impact of each element while (j < value.length - 1) { ans += (value[j] - prev) * (N - value[j + 1]); ans %= mod; prev = value[j]; j++; } } // Return the value return ans; } // Driver code let N = 5; let arr = [1, 2, 2, 3, 2]; // Function call console.log(valueOfSubarrays(N, arr)); |
7
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us