Sum of all sub arrays in O(n) Time

Objec­tive:  Given an array write an algorithm to find the sum of all the possible sub arrays.

Example:

int [] a = {1, 2, 3};

Output: Possible subarrays –
{1}, {2}, {3}, {1, 2} , {2, 3}, {1, 2, 3}
So sum = 1+ 2+ 3 + 3 + 5 + 6 = 20

Approach:

By generating all sub arrays:

As discussed in Print all sub arrays, find out all the sub arrays and then calculate the sum.

Time complexity: O(n^3)

Complete Code:


Output:

Sum of elements of sub arrays is: 50

Better Approach:

Let’s observe the behavior for array = {1,2,3,4}

All sub arrays are:

[1] , [1 2], [1 2 3], [1 2 3 4],

[2], [2 3], [2 3 4]

[3], [3 4]

[4]

  • No of occurrences for each element
    • 1 appears 4 times
    • 2 appears 6 times
    • 3 appears 6 times
    • 4 appears 4 times
  • For each element at first place – If we observe closely, element at first position, the sub arrays are
  • For 1 = [1] , [1 2], [1 2 3], [1 2 3 4] and for 2 = [2], [2 3], [2 3 4], for 3 = [3], [3 4] so for element 1, no of occurrence at first position will be equal to n (n=4) here.
  • Next element which is ‘2’ the number of occurrence at the first position will be one less than n. means n – 1, and so on
  • So for ith element in array will have appearances at the first position in all the sub arrays will be = (n-i).
  • So for the first position, occurrences are
    • 1 appears 4 times.
    • 2 appears 3 times.
    • 3 appears 2 times.
    • 4 appears 1 times.
  • From Step 1 if we subtract the number of occurrences in above step, the remaining occurrences are (i is the iteration index)
    • 1 = 0, n = 4, i = 0
    • 2 = 3, n = 4,  i = 1
    • 3 = 4, n = 4,  i = 2
    • 4 = 3, n = 4, i = 3
  • From the step above, the formula which will give this result will be = (n-i)*i
  • So Total number of occurrences for ith index element in array will be = (n-i) + (n-i)*I => (n-i)*(i+1)
  • So for array {1,2,3,4}
    • 1*(4-0)*(0+1) +
    • 2*(4-1)*(1+1) +
    • 3*(4-2)*(2+1) +
    • 4*(4-3)*(3+1) = 1*4 + 2*6 + 3*6 + 4*4 = 50

Time Complexity: O(n)

Complete Code:


Output:

Sum of elements of sub arrays is: 50

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: