Perfect Subarray
Practice
3.7 (28 votes)
Arrays
Data structures
Easy
One Dimensional
Prefix sum
Prefix Sum
Problem
72% Success 10661 Attempts 20 Points 1s Time Limit 256MB Memory 1024 KB Max Code
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$$
Submissions
Please login to view your submissions
Similar Problems
Points:20
44 votes
Tags:
1-D ArrayArraysData StructuresEasyeasy
Points:20
95 votes
Tags:
EasyImplementation
Points:20
58 votes
Tags:
ArraysData StructuresEasyOne-dimensionalPartial SumPrefix sumSegment Trees
Editorial