7

Sum of Count of Unique Numbers in all Subarrays

 1 year ago
source link: https://www.geeksforgeeks.org/sum-of-count-of-unique-numbers-in-all-subarrays/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Sum of Count of Unique Numbers in all Subarrays

Given an array of n integers, the task is to count the sum of unique numbers in all subarrays.

Examples:

Input: [2, 1, 2]
Output: 9
Explanation: There are total 6 subarrays which are [2], [2, 1], [2, 1, 2], [1], [1, 2], [2]. The count of unique numbers in these subarrays is 1, 2, 2, 1, 2, 1 respectively. The sum of count these numbers will be 9.

Input: [2, 1, 3, 2]
Output: 19

Naive approach: The basic way to solve the problem is as follows:

The idea is to generate all the subarrays and for each subarray count the unique numbers and calculate its sum. The unique numbers in each subarray can be computed with help of map.

Below is the implementation of the above approach:

// C++ program to find Sum of Count of Unique Numbers in all
// Subarrays
#include <bits/stdc++.h>
using namespace std;
// This function returns numbers of unique elements for
// subarray a[l...r]
int uniqueElementSubarray(vector<int>& a, int l, int r)
{
// To store frequency
unordered_map<int, int> mp;
// To count unique elements
int count = 0;
for (int i = l; i <= r; i++) {
mp[a[i]]++;
if (mp[a[i]] == 1) {
count++;
}
}
return count;
}
// Returns Sum of Count of Unique Numbers in all
// Subarrays
int countUniqueElements(vector<int> a)
{
int n = a.size();
// To store final answer
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Count the  number of unqiue elements from
// index i to index j and add to result.
res = res + uniqueElementSubarray(a, i, j);
}
}
return res;
}
// Driver code
int main()
{
int n = 4;
vector<int> a{ 2, 1, 3, 2 };
int ans = countUniqueElements(a);
cout << "Sum of Count of Unique Numbers in all "
"Subarrays: "
<< ans;
return 0;
}
Output
Sum of Count of Unique Numbers in all Subarrays: 19

Time Complexity: O(n^3) since we are processing n^2 subarrays with maximum length n.
Auxiliary Space: O(n)

Better Approach: To solve the problem follow the below idea:

For each index i, find the the sum of unique elements of all subarrays starting at index i . This can be done by starting at index i, and iterating until the end of the array, keep updating the number of unique elements accordingly and store its sum. Then add this sum to final answer for each i from 1 to n.

Below is the implementation of above approach:

// C++ program to find Sum of Count of Unique
// Numbers in all Subarrays
#include <bits/stdc++.h>
using namespace std;
// Returns Sum of Count of Unique Numbers
// in all Subarrays
int countUniqueElements(vector<int> a)
{
int n = a.size();
// To store final answer
int res = 0;
for (int i = 0; i < n; i++) {
// To store frequency
unordered_map<int, int> mp;
// To store number of unique elements
int count = 0;
// To store sum of unique numbers of
// all subbrays starting at index i.
int sum = 0;
for (int j = i; j < n; j++) {
mp[a[j]]++;
if (mp[a[j]] == 1)
count++;
sum = sum + count;
}
// Add sum of unique numbers of all
// subarrays starting at index i
// to final answer
res = res + sum;
}
return res;
}
// Driver code
int main()
{
int n = 4;
vector<int> a{ 2, 1, 3, 2 };
int ans = countUniqueElements(a);
// Function Call
cout << "Sum of Count of Unique Numbers in all "
"Subarrays: "
<< ans;
return 0;
}
Output
Sum of Count of Unique Numbers in all Subarrays: 19

Time Complexity: O(n^2), (The outer loop runs in O(n) time, and the inner loop runs in O(n), resulting in a total time complexity of O(n^2).)
Auxiliary Space: O(n)

Efficient Approach: To solve the problem efficiently follow the below idea:

For any element x in the array, the contribution of this element will be the number of subarrays in which the frequency of this element is atleast 1. Coversely, this will be equal to total subarrays minus the number of subarrays in x is not present. This contribution is added to the overall answer. By repeating the process for all elements, sum of unique numbers in all subarrays can be computed.

Follow the steps below to solve the problem:

  • For each unique element in the array: store the indexes at which the element appears.
  • Indexes of each element can be stored in a map of arrays.
  • For each element x in the map, let arr represent the array of indexes of x:
    • Calculate the contribution of x to the final answer using the formula:
      contribution = totalSubarrays - (sum of ((index difference * (index difference + 1)) / 2) ),
      where index difference is (arr[j]-arr[j-1]-1) for j ranges from 1 to size of arr array.
    • Add the contribution of the element to the final answer.
  • The Sum of contributions calculated is the final answer, representing the sum of unique numbers in all subarrays.

Below is the implementation of above approach:

// C++ program to find Sum of Count of Unique
// Numbers in all Subarrays
#include <bits/stdc++.h>
using namespace std;
// Returns Sum of Count of Unique Numbers
// in all Subarrays
int countUniqueElements(vector<int> a)
{
int n = a.size();
int total_subarrays = n * (n + 1) / 2;
// To store final answer
int res = 0;
// To store indexes of each element
unordered_map<int, vector<int> > mp;
// Iterate the array to store the index
for (int i = 0; i < n; i++) {
mp[a[i]].push_back(i);
}
// Iterate over the map to find the
// contribution of each unique element
for (auto x : mp) {
// Stores the indexes of element x
vector<int> arr = x.second;
arr.push_back(n);
// Stores the length of index array
int len = arr.size();
// To find contribution of element x
// in the final answer
int contribution = 0;
// To store previous index of element x
int p = -1;
for (int j = 0; j < len; j++) {
int index_difference = arr[j] - p - 1;
contribution += (index_difference
* (index_difference + 1))
/ 2;
p = arr[j];
}
// Add contribution of each unique element
// to final answer
res = res + (total_subarrays - contribution);
}
return res;
}
// Driver code
int main()
{
int n = 4;
vector<int> a{ 2, 1, 3, 2 };
int ans = countUniqueElements(a);
// Function Call
cout << "Sum of Count of Unique Numbers in all "
"Subarrays: "
<< ans;
return 0;
}
Output
Sum of Count of Unique Numbers in all Subarrays: 19

Time Complexity: O(n), since iteration of indexes of elements is done only once.
Auxiliary Space: O(n)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK