Find Sum of all unique sub-array sum for a given array.
Last Updated :
17 Aug, 2022
Given an array of n-positive elements. The sub-array sum is defined as the sum of all elements of a particular sub-array, the task is to find the sum of all unique sub-array sum.
Note: Unique Sub-array sum means no other sub-array will have the same sum value.
Examples:
Input : arr[] = {3, 4, 5}
Output : 40
Explanation: All possible unique sub-array with their sum are as:
(3), (4), (5), (3+4), (4+5), (3+4+5). Here all are unique so required sum = 40
Input : arr[] = {2, 4, 2}
Output : 12
Explanation: All possible unique sub-array with their sum are as:
(2), (4), (2), (2+4), (4+2), (2+4+2). Here only (4) and (2+4+2) are unique.
Method 1 (Sorting Based):
- Calculate the cumulative sum of an array.
- Store all sub-array sum in vector.
- Sort the vector.
- Mark all duplicate sub-array sum to zero
- Calculate and return totalSum.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
long long int findSubarraySum(int arr[], int n)
{
int i, j;
long long int cArray[n + 1] = { 0 };
for (i = 0; i < n; i++)
cArray[i + 1] = cArray[i] + arr[i];
vector<long long int> subArrSum;
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++)
subArrSum.push_back(cArray[j] -
cArray[i - 1]);
sort(subArrSum.begin(), subArrSum.end());
long long totalSum = 0;
for (i = 0; i < subArrSum.size() - 1; i++)
{
if (subArrSum[i] == subArrSum[i + 1])
{
j = i + 1;
while (subArrSum[j] == subArrSum[i] &&
j < subArrSum.size())
{
subArrSum[j] = 0;
j++;
}
subArrSum[i] = 0;
}
}
for (i = 0; i < subArrSum.size(); i++)
totalSum += subArrSum[i];
return totalSum;
}
int main()
{
int arr[] = { 3, 2, 3, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSubarraySum(arr, n);
return 0;
}
|
Java
import java.util.*;
class GFG{
static int findSubarraySum(int arr[], int n)
{
int i, j;
int cArray[] = new int[n + 1];
for(i = 0; i < n; i++)
cArray[i + 1] = cArray[i] + arr[i];
Vector<Integer> subArrSum = new Vector<Integer>();
for(i = 1; i <= n; i++)
for(j = i; j <= n; j++)
subArrSum.add(cArray[j] -
cArray[i - 1]);
Collections.sort(subArrSum);
int totalSum = 0;
for(i = 0; i < subArrSum.size() - 1; i++)
{
if (subArrSum.get(i) ==
subArrSum.get(i + 1))
{
j = i + 1;
while (subArrSum.get(j) ==
subArrSum.get(i) &&
j < subArrSum.size())
{
subArrSum.set(j, 0);
j++;
}
subArrSum.set(i, 0);
}
}
for(i = 0; i < subArrSum.size(); i++)
totalSum += subArrSum.get(i);
return totalSum;
}
public static void main(String[] args)
{
int arr[] = { 3, 2, 3, 1, 4 };
int n = arr.length;
System.out.print(findSubarraySum(arr, n));
}
}
|
Python3
def findSubarraySum(arr, n):
cArray = [0 for i in range(n + 1)]
for i in range(0, n, 1):
cArray[i + 1] = cArray[i] + arr[i]
subArrSum = []
for i in range(1, n + 1, 1):
for j in range(i, n + 1, 1):
subArrSum.append(cArray[j] -
cArray[i - 1])
subArrSum.sort(reverse = False)
totalSum = 0
for i in range(0, len(subArrSum) - 1, 1):
if (subArrSum[i] == subArrSum[i + 1]):
j = i + 1
while (subArrSum[j] == subArrSum[i] and
j < len(subArrSum)):
subArrSum[j] = 0
j += 1
subArrSum[i] = 0
for i in range(0, len(subArrSum), 1):
totalSum += subArrSum[i]
return totalSum
if __name__ == '__main__':
arr = [3, 2, 3, 1, 4]
n = len(arr)
print(findSubarraySum(arr, n))
|
C#
using System;
using System.Collections.Generic;
class GFG{
static int findSubarraySum(int []arr,
int n)
{
int i, j;
int []cArray = new int[n + 1];
for(i = 0; i < n; i++)
cArray[i + 1] = cArray[i] + arr[i];
List<int> subArrSum = new List<int>();
for(i = 1; i <= n; i++)
for(j = i; j <= n; j++)
subArrSum.Add(cArray[j] -
cArray[i - 1]);
subArrSum.Sort();
int totalSum = 0;
for(i = 0; i < subArrSum.Count - 1; i++)
{
if (subArrSum[i] ==
subArrSum[i + 1])
{
j = i + 1;
while (subArrSum[j] ==
subArrSum[i] &&
j < subArrSum.Count)
{
subArrSum[j] = 0;
j++;
}
subArrSum[i] = 0;
}
}
for(i = 0; i < subArrSum.Count; i++)
totalSum += subArrSum[i];
return totalSum;
}
public static void Main(String[] args)
{
int []arr = {3, 2, 3, 1, 4};
int n = arr.Length;
Console.Write(findSubarraySum(arr, n));
}
}
|
Javascript
<script>
function findSubarraySum(arr, n) {
var i, j;
var cArray = new Array(n + 1).fill(0);
for (i = 0; i < n; i++)
cArray[i + 1] = cArray[i] + arr[i];
var subArrSum = [];
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++) subArrSum.push(cArray[j] - cArray[i - 1]);
subArrSum.sort();
var totalSum = 0;
for (i = 0; i < subArrSum.length - 1; i++) {
if (subArrSum[i] == subArrSum[i + 1]) {
j = i + 1;
while (subArrSum[j] == subArrSum[i] && j < subArrSum.length) {
subArrSum[j] = 0;
j++;
}
subArrSum[i] = 0;
}
}
for (i = 0; i < subArrSum.length; i++) totalSum += subArrSum[i];
return totalSum;
}
var arr = [3, 2, 3, 1, 4];
var n = arr.length;
document.write(findSubarraySum(arr, n));
</script>
|
Complexity Analysis:
- Time Complexity: O(N^2 + N * logN)
- Auxiliary Space: O(N)
Method 2 (Hashing Based):
The idea is to make an empty hash table. We generate all subarrays. For every subarray, we compute its sum and increment count of the sum in the hash table. Finally, we add all those sums whose count is 1.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
long long int findSubarraySum(int arr[], int n)
{
int res = 0;
unordered_map<int, int> m;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += arr[j];
m[sum]++;
}
}
for (auto x : m)
if (x.second == 1)
res += x.first;
return res;
}
int main()
{
int arr[] = { 3, 2, 3, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSubarraySum(arr, n);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static int findSubarraySum(int []arr, int n)
{
int res = 0;
HashMap<Integer,
Integer> m = new HashMap<Integer,
Integer>();
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = i; j < n; j++)
{
sum += arr[j];
if (m.containsKey(sum))
{
m.put(sum, m.get(sum) + 1);
}
else
{
m.put(sum, 1);
}
}
}
for (Map.Entry<Integer,
Integer> x : m.entrySet())
if (x.getValue() == 1)
res += x.getKey();
return res;
}
public static void main(String[] args)
{
int arr[] = { 3, 2, 3, 1, 4 };
int n = arr.length;
System.out.println(findSubarraySum(arr, n));
}
}
|
Python3
def findSubarraySum(arr, n):
res = 0
m = dict()
for i in range(n):
Sum = 0
for j in range(i, n):
Sum += arr[j]
m[Sum] = m.get(Sum, 0) + 1
for x in m:
if m[x] == 1:
res += x
return res
arr = [3, 2, 3, 1, 4]
n = len(arr)
print(findSubarraySum(arr, n))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static int findSubarraySum(int []arr, int n)
{
int res = 0;
Dictionary<int,
int> m = new Dictionary<int,
int>();
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = i; j < n; j++)
{
sum += arr[j];
if (m.ContainsKey(sum))
{
m[sum] = m[sum] + 1;
}
else
{
m.Add(sum, 1);
}
}
}
foreach(KeyValuePair<int, int> x in m)
if (x.Value == 1)
res += x.Key;
return res;
}
public static void Main(String[] args)
{
int []arr = { 3, 2, 3, 1, 4 };
int n = arr.Length;
Console.WriteLine(findSubarraySum(arr, n));
}
}
|
Javascript
<script>
function findSubarraySum(arr, n)
{
let res = 0;
let m = new Map();
for(let i = 0; i < n; i++)
{
let sum = 0;
for(let j = i; j < n; j++)
{
sum += arr[j];
if (m.has(sum))
{
m.set(sum, m.get(sum) + 1);
}
else
{
m.set(sum, 1);
}
}
}
for(let x of m)
if (x[1] == 1)
res += x[0];
return res;
}
let arr = [ 3, 2, 3, 1, 4 ];
let n = arr.length;
document.write(findSubarraySum(arr, n));
</script>
|
Complexity Analysis:
- Time Complexity: O(N^2)
- Auxiliary Space: O(N)
Please Login to comment...