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$$
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
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor