All Tracks Data Structures Arrays 1-D Problem

Perfect Subarray
/

Arrays, Data Structures, One-dimensional, Prefix sum, prefix-sum

Problem
Editorial
Analytics

You are given an array $$A$$ of $$N$$ integers. You need to count the subarrays which have the sum of all elements in it a perfect square.

Input
The first line contains an integer $$N$$ that denotes count of elements in the array. Next line contains $$N$$ space separated integers that denote elements of the array.

Output
In the output, you need to print the count of subarrays for which the sum of elements is a perfect square.

Constraints
$$1 \le N \le 5000$$
$$1 \le A[i] \le 10^6$$

SAMPLE INPUT
4
1 4 2 3
SAMPLE OUTPUT
3
Explanation

The given array is: 1 4 2 3

Let us list the sum of all possible subarrays:

[1 , 1] = 1
[1 , 2] = 1 + 4 = 5
[1 , 3] = 1 + 4 + 2 = 7
[1 , 4] = 1 + 4 + 2 + 3 = 10
[2 , 2] = 4
[2 , 3] = 4 + 2 = 6
[2 , 4] = 4 + 2 + 3 = 9
[3 , 3] = 2
[3 , 4] = 2 + 3 = 5
[4 , 4] = 3

[1, 4, 9] = 3

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?