# PROBLEM LINK:

Div1, Div2Practice

**Author:**Misha Chorniy

**Tester:**Lewin Gan

**Editorialist:**Adarsh Kumar

# DIFFICULTY:

Easy-Medium# PREREQUISITES:

Sieve of Eratosthenes# PROBLEM:

You are given an array $A$ with size $N$. For each $K$ between $1$ and $N$ (inclusive), find out if it is possible to partition (split) the array $A$ into $K$ contiguous subarrays such that the sum of elements within each of these subarrays is the same.# EXPLANATION:

Let $S* = \sum_{j=1}^{i} A[j]$. Let's make some observation here now:- All the values of $S*$ will be distinct because all $A[j] > 0$.
- $S[N]$ must be divisible by $K$ if we want to partition the array into $K$ contiguous part.
- Sum of each part will be equal to $\frac{S[N]}{K} = X$ (say).
- For every multiple of $X$ i.e. for every $X*i$ ∀ $1 \le i \le K$ there must exist some $j$ such that $S[j]=X.i$.

Iterate over all the divisors of S[N] that is \le N. For every such divisor K we will check if all of the multiples of \frac{S[N]}{K} are present in the prefix sum array or not. Let’s make a cnt[] array which stores how many multiples of \frac{S[N]}{K} are present in the prefix sum array in cnt[K]. Any K will be good iff cnt[K]==K.

From the above observations, S[j]=\frac{S[N]}{K}.i which means \frac{S[j]}{S[N]}=\frac{i}{K}.

We are going to iterate over S[j], compute the irreducible fraction \frac{S[j]}{S[N]} =\frac{P}{Q}. Now we need to increase cnt[Q.i] by 1 for all those Q.i that are divisors of S[N] and \le N, because for every Q.i you get a distinct P.i because of the property that all prefix sums are distinct.

Doing the later step for every j can be costly. Hence, we will use sieve for this purpose. When iterating over j, just increment cnt[Q] by 1 if Q \le N. When done iterating over j, you can run a sieve-like algorithm for updating the multiples of every cnt[Q.i] which will cost us O(NlogN).

You can refer to the setter’s solution for implementation details of this approach.