### PROBLEM LINK

### DIFFICULTY

HARD

### PREREQUISITES

### PROBLEM

You are given an array of **N** positive integers. There are ** ^{N+1}C^{2}** 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 * 10^{10}

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(N ^{2} 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 answer = 0 for i = 1 to MAX_SUM answer += sums[i]

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(N ^{2} + 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 = x^{0}+ x^{S[1]}+ x^{S[2]}+ ... x^{S[N]}Y = x^{0}+ 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 **x ^{S[N]}** and check the coefficients of all the terms

**x**and above in th resultant polynomial.

^{S[N]+1}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.