Given an array of n-positive elements. 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 : 36
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 = 36Input : 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)
1- Calculate cumulative sum of array.
2- Store all sub-array sum in vector.
3- Sort the vector.
4- Mark all duplicate sub-array sum to zero
5- Calculate and return totalSum.
C++
// C++ for finding sum of all unique // subarray sum #include <bits/stdc++.h> using namespace std; // function for finding grandSum long long int findSubarraySum(int arr[], int n) { int i, j; // calculate cumulative sum of array // cArray[0] will store sum of zero elements 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; // store all subarray sum in vector for (i = 1; i <= n; i++) for (j = i; j <= n; j++) subArrSum.push_back(cArray[j] - cArray[i - 1]); // sort the vector sort(subArrSum.begin(), subArrSum.end()); // mark all duplicate sub-array // sum to zero 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; } } // calculate total sum for (i = 0; i < subArrSum.size(); i++) totalSum += subArrSum[i]; // return totalSum return totalSum; } // Driver Code int main() { int arr[] = { 3, 2, 3, 1, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findSubarraySum(arr, n); return 0; } |
Python3
# Python 3 for finding sum of all # unique subarray sum # function for finding grandSum def findSubarraySum(arr, n): # calculate cumulative sum of array # cArray[0] will store sum of zero elements cArray = [0 for i in range(n + 1)] for i in range(0, n, 1): cArray[i + 1] = cArray[i] + arr[i] subArrSum = [] # store all subarray sum in vector for i in range(1, n + 1, 1): for j in range(i, n + 1, 1): subArrSum.append(cArray[j] - cArray[i - 1]) # sort the vector subArrSum.sort(reverse = False) # mark all duplicate sub-array # sum to zero 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 # calculate total sum for i in range(0, len(subArrSum), 1): totalSum += subArrSum[i] # return totalSum return totalSum # Drivers code if __name__ == '__main__': arr = [3, 2, 3, 1, 4] n = len(arr) print(findSubarraySum(arr, n)) # This code is contributed by # Sahil_Shelangia |
41
Method 2 (Hashing Based) The idea is make an empty hash table. We generate all subarrays. For every subarray, we compute its sum and increment count of sum in hash table. Finally we add all those sums whose count is 1.
C++
// CPP for finding sum of all unique subarray sum #include <bits/stdc++.h> using namespace std; // function for finding grandSum long long int findSubarraySum(int arr[], int n) { int res = 0; // Go through all subarrays, compute sums // and count occurrences of sums. 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]++; } } // Print all those sums that appear // once. for (auto x : m) if (x.second == 1) res += x.first; return res; } // Driver code int main() { int arr[] = { 3, 2, 3, 1, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findSubarraySum(arr, n); return 0; } |
Python3
# Python3 for finding sum of all
# unique subarray sum
# function for finding grandSum
def findSubarraySum(arr, n):
res = 0
# Go through all subarrays, compute sums
# and count occurrences of sums.
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
# Print all those Sums that appear
# once.
for x in m:
if m[x] == 1:
res += x
return res
# Driver code
arr = [3, 2, 3, 1, 4]
n = len(arr)
print(findSubarraySum(arr, n))
# This code is contributed by mohit kumar
41
This article is attributed to GeeksforGeeks.org
leave a comment
0 Comments