Sum of all subarrays of an Array
Task:- Given an array A of N integers, find the sum of all the subarrays of A.
For eg:- A = [ 2, 3, 1, 5 ]
Sub-arrays of A are [2], [3], [1], [5], [2,3], [3,1], [1,5], [2,3,1], [3,1,5], [2,3,1,5]
The sum of all subarrays = 52
Brute Force Approach:- We can generate every subarray and calculate the sum of each subarray and add it to a variable.
Generating every subarray will take exponential time ( O(2^N) ).
So this approach is very naive and consumes a lot of time and space.
Better Approach:- We can use two for loops. The outer for loop with variable ‘i’ and inner for loop with variable ‘j’. We traverse the array and calculate the sum of subarray from i to j.
So i -> 0 to N-1
And j -> i to N-1.
At each step we add the A[j] to the subarray sum. Add that sum to the final variable let’s say ‘answer’.
The time complexity of this approach is O(N²) since for each element we are traversing till the end of the array.
Code:-
Efficient Approach:- We can observe some patterns about the frequency of each element in the final answer.
For eg: A=[1, 2, 3, 4]
All the subarrays are :
Length 1 → [1], [2], [3], [4]
Length 2 → [1,2], [2,3], [3,4]
Length 3 → [1,2,3], [2,3,4]
Length 4 → [1,2,3,4]
If we count the number of occurrences of each element. We can see that 1 occurs 4 times, 2 occurs 6 times, 3 occurs 6 times and 4 occurs 4 times. i.e -
1 → 4
2 → 6
3 → 6
4 → 4
In the same way for array of length 5, let’s say A=[1, 2, 3, 4, 5]
All the subarrays are :
Length 1 — → [1], [2], [3], [4], [5]
Length 2 — → [1,2], [2,3], [3,4], [4,5]
Length 3 — → [1,2,3], [2,3,4],[3,4,5]
Length 4 — → [1,2,3,4], [2,3,4,5]
Length 5 — → [1,2,3,4,5]
If we count the number of occurrences of each element. We can see that 1 occurs 4 times, 2 occurs 6 times, 3 occurs 6 times and 4 occurs 4 times. i.e -
1 → 5
2 → 8
3 → 9
4 → 8
5 → 5
That means for an array of fixed length N, the number of occurrences of each element in the sum of all subarrays are fixed and are in some pattern. Let’s derive a formula to get these occurrences.
We can call these number of occurrences as factors as after multiplying by the factors we get value/contribution of each element in the final answer.
For the above example:
The factor of element 1 = 5 = no of subarrays in which 1 is present
The factor of element 2 = 8 = no of subarrays in which 2 is present and so on.
So the number of subarrays in which 2 are present can be broken down to subarrays in which
{ 2 is the starting element of subarray} + {subarrays in which 2 is the last element of subarray} + {subarrays in which 2 is present in the middle}
1] For a given element at position i, the no of subarrays starting with that element will be (N-i) as there are (N-i) elements towards the right of that element (including i-th element).
For i=1 , A[i]=2 , N-i = 5–1 = 4
Subarrays are [2], [2,3], [2,3,4], [2,3,4,5]
No of subarrays starting at i = N — i
2] For a given element at position i, the no of subarrays starting with that element will be ( i ) as there are ( i ) elements towards left of that element.
For i=1 , A[i]=2
Subarrays are [1,2]
No of subarrays ending at i = i
3] For a given element at position i, the no of subarrays in which A[i] comes in the middle of some elements are ( no of elements before i)*(no of elements after i)
No of elements before i = i
No of elements after i = (N - i - 1)
(-1 because we do not count the i-th element itself)
For i=1, A[i]=2
Subarrays are [1,2,3], [1,2,3,4], [1,2,3,4,5]
No of subarrays with i in middle = i * (N - i - 1)
For an element at i-th position :
Using above formula, we can get factors array and then we multiply factors array with original array. The sum of resulting array would be the sum of all subarrays.
The time complexity of this approach is linear i.e- O(N) as we are calculating factors in constant (O(1)) time and calculating sum of the array.
Code:-
