Home » Interview coding problems/challenges

# All subarray Sum of an array

In this article, we are going to see **how to find all the subarray sums of an array?** This is an interview problem can be featured in an interview round.

Submitted by Radib Kar, on September 02, 2019

**Problem statement:**

Find sum of all subarray sums out of an array.

**Example:**

Input array: [1, 2, 3, 4] Output: 50

**Solution:**

Of course, there exists an easy solution where we can use three for loops with time complexity **(O (n3))**. The outer loop and intermediate loop are to iterate through all subarrays and the innermost one is to compute the sum. But here, we are not going to discuss this simple brute-force solution. Rather we will discuss an efficient way to minimize the time complexity.

Let's look at an example first,

Array = [1, 2, 3, 4] Sub-arrays are [1] =1 [2] =2 [3] =3 [4] =4 [1, 2] =1+2=3 [2, 3] =2+3= 5 [3, 4] =3+4 =7 [1, 2, 3] = 1+2+3= 6 [2, 3, 4] = 2+3+4= 9 [1, 2, 3, 4] = 1+2+3+4 = 10 Total sum= 50

Let's concentrate on finding appearance on each element while calculating the total sum

If we notice carefully, we can find that we have calculated

Sum of

4 1's = 4*1 = 4 6 2's = 6*2 = 12 6 3's = 6*3 = 18 4 4's = 4*4 = 16Which is 50

So, if we can come up with an algorithm to find occurrences of each element for an n-length array, then we can compute the total sum in O(n). WE don't even need to compute subarray sums specifically & separately.

So, is there any such algorithm? There is.

A sub-array is a group of contagious elements

Now,

- An element is a subarray can be the first element of the subarray.
- It can be an intermediate or end element of a sub-array starting for any previous element in the array.

So, there is two option.

Now consider option 1.

Say an element is at index i of an n-length array

Then, how many sub-arrays are there which start from the particular element(arr[i])?

Answer is (n-i), of course

As the subarrays of these type are:

[arr[i] ] //arr be the array name [arr[i], arr[i+1]] [arr[i], arr[i+1], arr[i+2] ] ... ... [arr[i], arr[i+1], arr[i+2], ..., arr[n-1]] // arr[n-1] is the last element So for option1 there is (n-i) occurences of the arr[i] already

Now consider option2,

There are i elements preceding the arr[i] (0-indexed, i-index element is actually (i+1)^{th}).

Now, arr[i] may be part of subarrays starting with any of this i (preceded) elements or may not be.

Like, for array

[1, 2, 3, 4]

Say i=2

arr[i]=3

arr[i] is part of sub-array [1,2,3] but not part of [1] or [1, 2] (both starting from 1 which is part of preceded elements).

Now the question is of how many subarrays of any preceded element, arr[i] is part of.

Answer is (n-i) as subarray containing arr[i](starting from any preced element) is similar to the number of subarray starting from arr[i].

Total number of occurrences for Option2 is then: i(n-i)

So, total occurrences of i-index element **(arr[i]) =(n-i) + i*(n-i) =(i+1)*(n-i)**

So, total sum can be calculated:

for i=1: n sum+= arr[i]* (i+1) * (n-i)

**Time complexity: O(n)**

### C++ implementation to find all subarray Sum of an array

#include <bits/stdc++.h> using namespace std; #define MAX 1000000007 long long int subarraysum(vector<int> arr, int n) { long long int sum = 0; long long int pro; //calculation of the formula derived //arr[i]*(i+1)*(n-i) for (int i = 0; i < n; i++) { pro = ((arr[i] % MAX) * (i + 1) % MAX) % MAX; pro = ((pro % MAX) * ((n - i) % MAX)) % MAX; sum = ((sum % MAX) + (pro % MAX)) % MAX; } return sum; } int main() { int n, item; cout << "enter array length\n"; cin >> n; vector<int> arr; cout << "enter elements\n"; for (int j = 0; j < n; j++) { cin >> item; arr.push_back(item); } cout << "Total subarray sum=> " << subarraysum(arr, n) << endl; return 0; }

**Output**

enter array length 4 enter elements 1 2 3 4 Total subarray sum=> 50

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL