Counting Algorithms to Compute All Sublists Sum

Given a list of integers nums, consider every contiguous sublist. Sum each of these sublists and return the sum of all these values. Mod the result by 10 ** 9 + 7.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [2, 3, 5]
Output
33
Explanation
We have the following subarrays:
[2]
[3]
[5]
[2, 3]
[3, 5]
[2, 3, 5]
The sum of all of these is 33.

Bruteforce Algorithm to Compute All Sublists Sum

Sure we can bruteforce, by O(N^2) to list all sub lists and another O(N) to compute the sum – this is inefficient as the overall complexity is O(N^3).

1
2
3
4
5
6
7
8
9
10
11
12
13

int allSubListSum(vector<int>& nums) {
    int64_t ans = 0;
    int M = 1e9+7;
    int n = static_cast<int>(nums.size());
    for (int i = 0; i < n; ++ i) {
        for (int j = i; j < n; ++ j) {
            for (int k = i; k <= j; ++ k) {
                ans = (ans + nums[k]) % M;
            }
        }        
    }
    return ans;
}

int allSubListSum(vector<int>& nums) {
    int64_t ans = 0;
    int M = 1e9+7;
    int n = static_cast<int>(nums.size());
    for (int i = 0; i < n; ++ i) {
        for (int j = i; j < n; ++ j) {
            for (int k = i; k <= j; ++ k) {
                ans = (ans + nums[k]) % M;
            }
        }        
    }
    return ans;
}

A better bruteforce would improve to O(N^2) quadratic where we accumulate/update the sum:

1
2
3
4
5
6
7
8
9
10
11
12
13

int allSubListSum(vector<int>& nums) {
    int64_t ans = 0;
    int M = 1e9+7;
    int n = static_cast<int>(nums.size());
    for (int i = 0; i < n; ++ i) {
        int64_t curSum = 0;
        for (int j = i; j < n; ++ j) {
            curSum += nums[j];
            ans = (ans + curSum) % M;
        }        
    }
    return ans;
}

int allSubListSum(vector<int>& nums) {
    int64_t ans = 0;
    int M = 1e9+7;
    int n = static_cast<int>(nums.size());
    for (int i = 0; i < n; ++ i) {
        int64_t curSum = 0;
        for (int j = i; j < n; ++ j) {
            curSum += nums[j];
            ans = (ans + curSum) % M;
        }        
    }
    return ans;
}

Math Counting Algorithm to Compute the All Sublist Sum

A better approach in O(N) linear time would be to count How many times does each integer appear in the final sum. We can easily get that for index i, it appears (i + 1) which ends at it or (n – i) which starts at it. Thus, we can iterate the array for each number and multiply by their occurence in the sublists.

1
2
3
4
5
6
7
8
9

int allSubListSum(vector<int>& nums) {
    int64_t ans = 0;
    int M = 1e9+7;
    int n = static_cast<int>(nums.size());
    for (int i = 0; i < n; ++ i) {
        ans = (ans + (int64_t)nums[i] * (i + 1) * (n - i)) % M;
    }
    return ans;
}

int allSubListSum(vector<int>& nums) {
    int64_t ans = 0;
    int M = 1e9+7;
    int n = static_cast<int>(nums.size());
    for (int i = 0; i < n; ++ i) {
        ans = (ans + (int64_t)nums[i] * (i + 1) * (n - i)) % M;
    }
    return ans;
}

–EOF (The Ultimate Computing & Technology Blog) —