Find Sum of all unique sub-array sum for a given array

Difficulty Level Easy
Frequently asked in Amazon Facebook GreyOrange Intuit Microsoft Nagarro
Array Hash SortingViews 2221

Suppose you have an array of integers. The problem “Find Sum of all unique sub-array sum for a given array” asks to find out the sum of all unique sub-arrays (Sub-array sum is the sum of each sub-array’s elements).

By unique sub-array sum, we meant to say that no sub-array has the same value.

Example

arr[] = {3, 1, 4, 5}
44
arr[] = {2,1,3,6}
36

Find Sum of all unique sub-array sum for a given array

Algorithm

  1. Declare a map.
  2. Set output to 0.
  3. Traverse the array from i=0, to i<n(length of the array).
    1. Set the sum to 0.
    2. Traverse the array from j=i, to j<n(length of the array).
      • Add the value of arr[j] to the sum into the sum.
      • Add the sum and its occurrence into the map.
  4. Traverse the map and check for those key’s entries whose value is 1.
    1. Add the value of keys to the output whenever we find the condition satisfied.
  5. Return output.

Explanation

We are given an integer array. Our task is to find out the sum of all the unique sub-arrays. The sum of each sub-array will be the sum of each sub-array’s element. We are going to use hashing to solve this question. We will be picking up each element of an array, initializing sum to 0, whenever we change the value of i. When we enter the inner loop, we will traverse an array from i to n, and adding up each value of array and sum. Then we simultaneously store the sum and its occurrence in the map. After visiting the whole array, find out all the possible sum of sub-arrays. After that, we look for those sums in the map whose occurrence is only once. Because we want the sum of unique sub-arrays, means which have distinct sums. So when we find the sum in the map which occurs once, meant to say whose frequency is 1, we will add and update the value of those sums into the output.

Considering an example for it:

Example

arr[] = { 3, 1, 4, 5}

First, we have i=0, then we have 3 as an element and we will start from 3, we will be adding 3 into the sum and update 3 into the map, then adding 1 into the sum, and updating  4 into the map, then taking 4 as an element into the sum and adding 7 into the map. In this way, we will end up the first traversal after visiting 5 and updating 12 into the map.

So when we take 4 as an element and starting from 4, we will update the sum into the map, since, 4 is already in the map, we will just increase its frequency, and we will ignore those sums whose frequency is not 1. In this way, we will be able to handle unique sub-arrays.

Code

C++ code to find sum of all unique sub-array sum for a given array

#include<iostream>
#include<unordered_map>

using namespace std;

int findSumOfUnique(int arr[], int n)
{
    int output = 0;
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            MAP[sum]++;
        }
    }
    for (auto entry : MAP)
        if (entry.second == 1)
            output += entry.first;

    return output;
}
int main()
{
    int arr[] = { 3, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSumOfUnique(arr, n);
    return 0;
}

44

Java code to find sum of all unique sub-array sum for a given array

import java.util.HashMap;
import java.util.Map;

class SumUniqueSubArray
{
    public static int findSumOfUnique(int []arr, int n)
    {
        int output = 0;

        HashMap<Integer,Integer> MAP = 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 (MAP.containsKey(sum))
                {
                    MAP.put(sum, MAP.get(sum) + 1);
                }
                else
                {
                    MAP.put(sum, 1);
                }
            }
        }
        for (Map.Entry<Integer,Integer> entry : MAP.entrySet())
            if (entry.getValue() == 1)
                output += entry.getKey();

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {3, 1, 4, 5};
        int n = arr.length;
        System.out.println(findSumOfUnique(arr, n));
    }
}

44

Complexity Analysis

Time Complexity

O(n2) where “n” is the number of elements in the array. Because we have used 2 nested loops and searching for sum is done in O(1) using HashMap.

Space Complexity

O(n^2) where “n” is the number of elements of the array. Because in the worst case we may have n^2 different sub-array sum.

Translate »