Subarray is one of the most common topics that is asked during an interview. Many companies like Amazon, Microsoft, and Google ask questions about subarrays either directly or indirectly by using them as a part of the question. So an individual needs to have a clear understanding of this topic.
In this blog, we will discuss one of the subarrays' famous and fundamental problems. We will discuss various approaches to solve this question. We will start from brute source and move to a more optimized approach. So, let’s get on with our topic without wasting further time.
Problem Statement
You are given an array A of size N. You have to find the sum of all the subarrays that have the unique sum. Here unique sum refers to the sum which occurs only one time in all the subarrays or the sum which is not repeated.
Constraints
1<=N<=10^6
1<=A[i]<=10^7
Before deep-diving into the solution to this problem, we should look at some examples to help us understand the problem better.
Examples
Input:
A[]={2,4,6}
Output:
Sum = 28
Explanation:
For the above array the subarrays will be{2}, {4}, {6}, {2,4}, {4,6}, {2,4,6}. But among all the subarrays the unique subarrays are {2}, {4}, {4,6}, {2,4,6} which adds as 2+4+4+6+2+4+6=28.
Input:
A[]={1,8,5,6,2}
Output:
Sum = 130
Input:
A[]={2,5,2}
Output:
Sum = 14
Brute Force Approach(Using Sorting)
The brute force approach uses sorting to solve this question. We will find the sum of all the subarrays and store them in a vector, and from that vector, we will make the repeating sum as 0 and calculate the sum of the rest of the vector that will be our answer.
Algorithm
To solve this problem, we will create a function name solve where we pass two arguments the given array and its size.
After naming the function, we will initialize a vector name suntillCurrentPos which will store the sum of the array till the current index.
Now we will travel through the subarrays using two nested loops and store the sum of all the subarrays in a vector named AllSubArrSum.
Sort the vector and then start to travel in the vector.
While traversing the vector, if you find any sum repeating, then make that sum as 0 along with all its occurrences.
Now calculate the sum of the elements of the vector. It will be your answer.
Code in C++
#include <bits/stdc++.h>
using namespace std;
long long int solve(int a[], int n)
{
int i, j;
// SumTillCurrentPos will store the sum of array till current position.
vector<long long int>SumTillCurrentPos(n+1,0);
for (i = 0; i < n; i++)
SumTillCurrentPos[i + 1] = a[i]+SumTillCurrentPos[i];
vector<long long int> AllsubArrSum;
// store all subarray sum in vector
for (i = 1; i < n+1; i++)
for (j = i; j < n+1; j++)
AllsubArrSum.push_back(SumTillCurrentPos[j] -
SumTillCurrentPos[i - 1]);
// sort the vector
sort(AllsubArrSum.begin(), AllsubArrSum.end());
// travel to every subarray and mark the subarray with duplicate sum as 0.
long long Uniquesum = 0;
for (i = 0; i < AllsubArrSum.size() - 1; i++)
{
if (AllsubArrSum[i] == AllsubArrSum[i + 1])
{
j = i + 1;
while (j < AllsubArrSum.size()&&AllsubArrSum[j] == AllsubArrSum[i])
{
AllsubArrSum[j] = 0;
j++;
}
AllsubArrSum[i] = 0;
}
}
// calculate the unique sum as the duplicate sum are
//set to 0 so they will not contribute in unique sum.
for (i = 0; i < AllsubArrSum.size(); i++)
Uniquesum += AllsubArrSum[i];
// return Uniquesum
return Uniquesum;
}
int main()
{
int n=6;
int a[n] = {5,3,1,6,7,5};
cout <<"The sum of all the unique subarrays sum of the given array is: " <<solve(a, n);
return 0;
}
Input:
A[]={5, 3, 1, 6, 7, 5}
Output:
The Sum of all the unique subarrays sum of the given array is: 176
Algorithm Complexity
Time Complexity: O(N^2)+O(N*logN)
Here we are traversing in two nested loops that will be O(N^2), and for sorting the vector, it will be (N*logN).
Space Complexity: O(N)
We are creating two vectors of size N that will contribute to a space complexity of O(N).
This approach is optimized because we do not need to sort the vector that contains the sum of all the subarrays. We do not have to traverse two to three times. The number of iterations is reduced. Here we will use hashing as we store the sum of all the subarrays in a hash table with their frequencies, and in the answer, we will add only the sum with frequency one and return the answer.
Algorithm
To solve this problem, we will create a function name solve where we pass two arguments the given array and its size.
After naming the function, we will create an unordered_map mp that will store the sum of all the subarrays with their frequencies.
Now start traversing in all the subarrays, calculate the sum of all the subarrays, and increase the value of that sum frequency in the unordered_map.
Now we will iterate in the map and check for the sum with frequency one and add that sum to our answer, and after iterating, return the answer.
Code in C++
#include <bits/stdc++.h>
using namespace std;
long long int solve(int a[], int n)
{
int ans = 0;
unordered_map<int, int> mp;
for (int i = 0; i < n; i++) {
// every time when moving to a new subarray we are initializing the sum as zero
int sum = 0;
for (int j = i; j < n; j++) {
sum += a[j];
// increasing the frequency of sum in the map
mp[sum]++;
}
}
// traversing the unordered map
for (auto itr : mp)
if (itr.second == 1)
// adding the sum which only appears once in our answer.
ans += itr.first;
return ans;
}
int main()
{
int n=6 ;
int a[n] = {5,3,1,6,7,5};
cout <<"The sum of all the unique subarrays sum of the given array is: " <<solve(a, n);
return 0;
}
Input:
A[]={5, 3, 1, 6, 7, 5}
Output:
The Sum of all the unique subarrays sum of the given array is: 176
Algorithm Complexity
Time Complexity: O(N^2)
We are traversing the array by two nested loops to find the sum of all the subarrays that will contribute to the O(N^2) in time complexity. Rest operations are not even of linear complexity.
Space Complexity: O(N)
Here, we are using an additional space to create an unordered_map that will take O(N) space in the worst case.
How many total subarrays can be formed from an array of size N?
From an array of size N, you can form N*(N+1)/2 subarrays.
How do we store values in a hash table?
In the hash table, we store values in the form of key-value pairs.
Which among the two, map or unordered_map uses hashing to store elements?
The unordered_map uses hashing to store the elements.
What is the time complexity of hashing?
The overall time complexity of the hash function is O(1).
Why is hashmap preferred over hashtable in some scenarios?
Usually, they both are preferred equally, but in the case of NULL keys, hashmap can store them, whereas hashtable cannot store NULL keys.
Conclusion
In this article, we have discussed the problem of finding the sum of all unique subarray sum problems. We have discussed two approaches for this problem: the brute force approach(sorting approach) and the optimized approach(using hashing). We have also discussed all the approaches' time and space complexities.
We hope you have gained a better understanding of the solution to this problem, and now it is your responsibility to solve it and try some new and different approaches. You can also try solving other array related problems such as Sum Of Two Arrays, Intersection Of Two Arrays etc.
38+ registered 
