patternMinor
Counting number of sums from contiguous subarrays of an array
Viewed 0 times
numbercountingsubarraysarraycontiguousfromsums
Problem
We are given an array $a[1 \ldots n]$ with all $a[i]>0$.
Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a[j\ldots k]$ for some $j,k$, the sum is the sum of all of the elements of the subarray). For example, if $a=[1,2,1]$, then the answer is 4: we can form $ 1,2,3,4$.
I know how to count the number of distinct sums in $O(n^2)$ time.
Furthermore, I have come to realise this is similar to the classical problem where we need to find the number of distinct substrings of a string. I was thinking of the possibility of constructing a suffix array and solving it in a similar fashion (in $O(n)$ time). But I have not been able to figure out how to modify that to work here. For example, if we use suffix array for $a=[1,2,1]$ we will get 5 cases instead of the four acceptable ones. Is this possible to do this using suffix arrays or am I thinking in the wrong direction?
Also there is one more direction I have been thinking in. Divide and conquer. Like if I divide the array into two parts every time until it is reduced to a single element. A single element can have one sum. Now if we combine two single elements, It can be done in two ways: if both single ranges have same element then we get 2 different sums, or if both have different elements we get 3 different sums. But I am not being able to generalize this for merging arrays of length greater than 1. Is it possible to merge two m size arrays and get the answer in $O(m)$?
Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a[j\ldots k]$ for some $j,k$, the sum is the sum of all of the elements of the subarray). For example, if $a=[1,2,1]$, then the answer is 4: we can form $ 1,2,3,4$.
I know how to count the number of distinct sums in $O(n^2)$ time.
Furthermore, I have come to realise this is similar to the classical problem where we need to find the number of distinct substrings of a string. I was thinking of the possibility of constructing a suffix array and solving it in a similar fashion (in $O(n)$ time). But I have not been able to figure out how to modify that to work here. For example, if we use suffix array for $a=[1,2,1]$ we will get 5 cases instead of the four acceptable ones. Is this possible to do this using suffix arrays or am I thinking in the wrong direction?
Also there is one more direction I have been thinking in. Divide and conquer. Like if I divide the array into two parts every time until it is reduced to a single element. A single element can have one sum. Now if we combine two single elements, It can be done in two ways: if both single ranges have same element then we get 2 different sums, or if both have different elements we get 3 different sums. But I am not being able to generalize this for merging arrays of length greater than 1. Is it possible to merge two m size arrays and get the answer in $O(m)$?
Solution
You almost surely can't get better than $O(n^2)$ in the worst case since the number of different sums can be in $\Theta(n^2)$.
Consider e.g. the array $[1,2,4,8,\dotsc, 2^n]$. Here each of the $\frac{n(n+1)}2$ contiguous subarrays has a different sum.
The "almost surely" is due to the fact that the problem does not require the values of the sums as output. However, I don't think duplicates can be avoided without determining at least most of the values.
Consider e.g. the array $[1,2,4,8,\dotsc, 2^n]$. Here each of the $\frac{n(n+1)}2$ contiguous subarrays has a different sum.
The "almost surely" is due to the fact that the problem does not require the values of the sums as output. However, I don't think duplicates can be avoided without determining at least most of the values.
Context
StackExchange Computer Science Q#13262, answer score: 2
Revisions (0)
No revisions yet.