Count the most common occurrence of subarray sum.

Constraints:

N <= 1e6; abs(ai) <= 1e6

Ex:

Inp:

5

1 1 2 1 4

Out:

3 (there are 3 subarray with the sum of 4: (1, 1, 2), (1, 2, 1), (4)

This question appears in ones of my friends competition and I have no idea how to solve it. Can someone help? Thanks.

Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).Any link?

I don't have one. It's an offline competition. (It could be impossible for all I know)

Reminds me the problem: subarray sum equals k. U can solve this problem for each different sum and then check for which k the frequency Is maximized. For some small constraint It Will work. In pretty sure there Is some clever solution btw...

Might be but for the worse, you can just solve it in n^2, since iterating for all the sums and kadanes is worse than n^2, I don't have idea for a better solution

I think it's unsolvable under the given constraints (it looks harder than FFT).

I will try to ask my friend to reach the authors :)). Thanks

do you mean ∑abs(ai)<=1e6?

The original problem says for a single element ai. But the problem itself is probably wrong.

Can you ask them the solution? If they have any of course.

Even if the sum of the values is small, isn't the solution $$$O(n + m \log^2 m)$$$ (where $$$m = \sum |a_i|)$$$? You have to compute only the differences such that $$$i < j$$$, and iirc this is only possible with FFTs of total length $$$O(m \log m)$$$.

i didn't get why it was m log^2 m,

i think i need here is a prefix sum, a convolution and an exclusion. it's n log n

I'm not sure is there sth I missed.

The convolution actually calculates the most frequent absolute value of a subarray sum (each subarray contributes to two sums, with opposite signs). You need D&C if you only want sums with the correct sign.

(What's an "exclusion"? Am I missing something?)

oh ! oh ! you are right.

Single fft cannot distinguish positive and negative perfix

why are there so many downvotes in your comments? The community not know the correct answer