Count of subarrays whose sum is a perfect square | C # code for the above approach . ; Function to find count of subarrays whose sum is a perfect square . ; To search for index with ( current prefix sum - j * j ) ; Storing the prefix sum ; Used to track the minimum value in prefixSum ; Calculating the prefixSum and tracking the prefixMin ; Below statement is used if array contains negative numbers ; Counts the no of subarrays with perfect square sum ; As 0 is a perfect square , so we initialize 0 th index - key with value 1 ; Here we count the perfect square subarray sum by searching if there is a prefix with sum = ( current prefixSum - ( sq * sq ) ) ; Increasing our subarray count ; Increasing the current prefixSum index value in map by 1 to count the other perfect squares while traversing further ; Driver code ; Printing the result
using System ; using System . Collections . Generic ; class GFG { static long countSubarrays ( int [ ] arr , int n ) { Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; int [ ] prefixSum = new int [ n ] ; int prefixMin = 0 ; prefixSum [ 0 ] = arr [ 0 ] ; prefixMin = Math . Min ( prefixMin , prefixSum [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { prefixSum [ i ] = prefixSum [ i - 1 ] + arr [ i ] ; prefixMin = Math . Min ( prefixMin , prefixSum [ i ] ) ; } long countSubs = 0 ; mp . Add ( 0 , 1 ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; prefixSum [ i ] - j * j >= prefixMin ; j ++ ) { if ( mp . ContainsKey ( prefixSum [ i ] - j * j ) ) countSubs += mp [ prefixSum [ i ] - j * j ] ; } if ( mp . ContainsKey ( prefixSum [ i ] ) ) { mp [ prefixSum [ i ] ] ++ ; } else { mp . Add ( prefixSum [ i ] , 1 ) ; } } return countSubs ; } public static void Main ( String [ ] args ) { int [ ] arr = { 2 , 3 , - 5 , 6 , - 7 , 4 } ; int n = arr . Length ; long ans = countSubarrays ( arr , n ) ; Console . Write ( ans ) ; } }