×

HARD

# PREREQUISITES

Fast Fourier Transform

# PROBLEM

You are given an array of N positive integers. There are N+1C2 sub-arrays of this array. Find the number of unique sums possible among all the possible sub-arrays.

# QUICK EXPLANATION

Although the problem statement isn't as direct as the problem description used above, it is very easy to come to the conclusion that this is indeed what the problem to be solved is.

The limits to the problem were given rather innovatively as

1 ≤ N * S ≤ 4 * 1010


Where S is the sum of all the numbers.

Considering all the numbers are positive, the real limit on N is hence

1 ≤ N ≤ 200,000


We note that S can vary greatly as N varies and hence we cannot solve this problem for all values of N under the same algorithm. We break our solution into 3 different methods meant to solve the problem for different values of N.

# EXPLANATION

## 1 ≤ N ≤ 2,000

For this limit of N

• The number of sub-arrays to be considered are at most 2,001,000
• The value of the sums can be at most 40,000,000,000 (for N = 1)

We can generate all the sums and eliminate the duplicates. We cannot eliminate them using a lookup table because of the possibly large value for the sums.

The complexity of this procedure would be O(N2 log N). The complexity is driven by the procedure to sort before we eliminate the duplicates.

sums = []

for i = 1 to N
value = 0
for j = i to N
value += A[j]
sums.push(value)

sort(sums)
eliminate-duplicates(sums)


## 2,000 < N ≤ 20,000

For this limit of N

• The number of sub-arrays to be considered are at most 200,010,000
• The value of the sums can be at most 20,000,000 (for N = 2000)

We can still generate all the sums and eliminate the duplicates. Note that sorting to eliminate the duplicates can be quite expensive since we are potentially considering over hundred million values. Fortunately, the value of sums has come down within the range to maintain a lookup table!

sums[] = { 0 }

for i = 1 to N
value = 0
for j = i to N
value += A[j]
sums[value] = 1

for i = 1 to MAX_SUM


The lookup table helped us avoid the cost of the sorting step to eliminate duplicates. We still relied upon our ability to iterate over every possible sub-array's sum. The complexity of this procedure is O(N2 + S).

## 20,000 < N ≤ 200,000

For this value of N

• The number of sub-arrays to be considered are at most 20,000,100,000
• The value of the sums can be at most 2,000,000 (for N = 20000)

We can no longer iterate over each sub-array because there could be too many of them. But we note that the value of the maximum possible sum is now very manageable. We can use this to our advantage by trying to base our approach completely over the possible values for sums.

Let us consider an array of sums of prefixes

S[i] = sum( A[x] : 1 ≤ x ≤ i )


We wish to find all the possible values generated by

S[j] - S[i]


for each 1 ≤ j ≤ N AND 1 ≤ i < j. This convolution can be generated by the product of the following two polynomials

X = x0 + xS[1] + xS[2] + ... xS[N]
Y = x0 + x-S[1] + x-S[2] + ... x-S[N]


The number of terms in the product of X and Y, which have non-zero coefficient and positive power, is the answer we are looking for. To only deal with positive powers in our problem, we can multiply Y with xS[N] and check the coefficients of all the terms xS[N]+1 and above in th resultant polynomial.

The fastest way to multiply two polynomials is using FFT. We can multiply the two polynomials as follows.

fX = FFT(X)
fY = FFT(Y)

fT = fX . fY (dot product)

T = iFFT(fT)


Thus, we can solve this case in O(N + S log S) time.

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

 3 I think that you can skip FFT(Y) step since its coefficients are essentially conjugates of FFT(X) answered 22 Jul '13, 13:14 6★lutyj 46●4 accept rate: 0%
 0 Isnt the complexity O(N + N log N) because each polynomial has N terms. answered 07 Dec '14, 03:27 41●1●2●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,639
×1,343
×1,186
×334
×20

question asked: 22 Jul '13, 01:07

question was seen: 6,102 times

last updated: 07 Dec '14, 03:27