This post is completed by 2 users

Add to List 
254. Sum of all sub arrays in O(n) Time
Objective: Given an array write an algorithm to find the sum of all the possible subarrays.
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:
As discussed in Print all sub arrays, find out all the subarrays, and then calculate the sum.
Time complexity: O(n^3)
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.
 The next element which is ‘2’ the number of occurrences at the first position will be one less than n. means n – 1, and so on
 So for i^{th} element in the array will have appearances at the first position in all the subarrays will be = (ni).
 So for the first position, occurrences are
 1 appears 4 times.
 2 appears 3 times.
 3 appears 2 times.
 4 appears 1 time.
 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 = (ni)*i
 So Total number of occurrences for ith index element in array will be = (ni) + (ni)*I => (ni)*(i+1)
 So for array {1,2,3,4}
 1*(40)*(0+1) +
 2*(41)*(1+1) +
 3*(42)*(2+1) +
 4*(43)*(3+1) = 1*4 + 2*6 + 3*6 + 4*4 = 50
Time Complexity: O(n)
Output:
Sum of elements of sub arrays is: 50