I am new to the concept of Fast Fourier Transformation. So I looked up at the codes of few very good coders like Ankit Shrivastava. In the solution of Ankit Shrivastava with solution link : CodeChef: Practical coding for everyone - and a few other successful submissions. I found that all the coders are doing the naive approach for the smaller values like <5000 values using HashSet and then for the larger values they are doing the Fast Fourier Transformation using their own classes of FFT. But if we try to submit the solution directly without this constraint and apply FFT to all the values of input we get NZEC as I tested on the solution of Ankit Shrivastava. I am unable to figure out the problem with this. Thank You
1 Like
In this problem FFT is used to generate all the possible differences of prefix sums. As all the positive values of such differences will give us the sub-array sum. We do this by multiplication of two polynomials, one with positive prefix sums as powers of x and the other with negative prefix sums as the powers of x. Since values of prefix sums can become very high for smaller values according to the problem constraint. So, this may cause excessive memory which causes NZEC.