Problem: Sum of All Subarrays

*Difficulty: Medium

Given an array A with N elements , you need to find the sum all sub arrays of array A. Since the sum could be very large print the sum modulo (10^9+7).

Input :
The first line contains integer T, denoting number of test cases. The first line of each test case contains an integer N, denoting the number of elements.The second line of each test case contains N space separated integers denoting values of the array A.
Output :
Print the answer of each test case in a new line.

Constraints :
1<=T<=10
1<=N<=10^5

Example
Input :

2
3
1 2 3
2
1 3

Output :
20
8

*Approach 1:

Generate all sub arrays
This is O(n^3) complexity solution

Code: Python 2.7

def sum_all_sub_arrs(arr):
    if len(arr) == 1:
        return arr[0]
    elif len(arr) == 2:
        return arr[0] + arr[1] + sum(arr)
    elif len(arr) == 3:
        return sum(arr)*2 + arr[0] + arr[1] + arr[1] + arr[2]
    else:
        sum_all = 0
        for i in range(2, len(arr)):
            for j in range(len(arr)):
                #print arr[j:j+i]
                sum_all += sum(arr[j:j+i])
                if j+i == len(arr):
                    break
        return sum_all + sum(arr)*2

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = input()
        arr = map(int, raw_input().strip().split())
        print sum_all_sub_arrs(arr) % (10**9+7)

It cant be applied to solve this problem, since if using C++, I can barely pass this problem with runtime nearly reach 5 seconds. (This is Python, so it’s impossible)

After 30 minutes working on papers, I figured out something’s interesting.
Example with input array’s length is odd
Array: 1 2 3 4 5
Sum of all sub-arrays:
1 + 2 + 3 + 4 + 5 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 1 + 2 + 3 + 2 + 3 + 4+ 3 + 4 + 5 + 1 + 2 + 3 + 4 + 2 + 3 + 4 + 5 + 1 + 2 + 3 +4 + 5 = 105
Here’s is the array and the number of times of each element in the equation above:
Array:              1 – 2 – 3 – 4 – 5
Frequency:     5 – 8 – 9 – 8 – 5
Example with input array’s length is even
Array: 1 2 3 4
Sum of all sub-arrays:
1 + 2 + 3 + 4 + 1 + 2 + 2 + 3 + 3 +4 + 1 +2 +3 + 2 + 3 + 4 + 1 +2 + 3 + 4 = 50
Array:           1 – 2 – 3 – 4
Frequency: 4 – 6 – 6 – 4
In general:
+ if length of input array is odd, and n is the length
Frequency: n –  prev+(n-2)  – prev+(n-4) – … – prev+1  – … – prev+(n-4)  – prev+(n-2) – n
+ if length of input array is even, and n is the length
Frequency: n – prev+(n-2) – prev+(n-4) – ….. – prev+(n-4) – prev+(n-2) – n

Code: Python 2.7

def sum_all_sub_arrs(arr):
    # input array contains only one element
    if len(arr) == 1:
        return arr[0]
    # init steps
    frequency = [0]*len(arr)
    dif = len(arr)-2
    # because frequency values are symmetric
    # example: 4 6 6 4
    #          3 4 3
    #          etc
    # we need to traverse only half first of the input array
    # and work out the frequency of each value
    for i in range(0, len(arr)//2 + 1 if len(arr) % 2 != 0 else len(arr)//2):
        # first frequency = len(arr)
        if i == 0:
            frequency[i] = len(arr)
        # then, each of next element is its previous cell plus difference
        # and decrease the difference by 2
        else:
            frequency[i] += (frequency[i-1] + dif)
            dif -= 2
    # half left of frequency
    for i in range(len(arr)//2+1 if len(arr) % 2 != 0 else len(arr)//2, len(arr)):
        offset = len(arr) - i - 1 
        frequency[i] = frequency[offset]
    return sum(x*y for (x,y) in zip(arr, frequency))

if __name__ == '__main__':
    t = input()
    mod = 10**9 + 7
    for _ in range(t):
        n = input()
        arr = map(int, raw_input().strip().split())
        print sum_all_sub_arrs(arr) % mod

Solution took: 94ms

Advertisements