Count of subarrays whose sum is a perfect square | 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 ; Prleting the result
function countSubarrays ( arr , n ) { let mp = new Map ( ) ; let prefixSum = Array . from ( { length : n } , ( _ , i ) => 0 ) ; let prefixMin = 0 ; prefixSum [ 0 ] = arr [ 0 ] ; prefixMin = Math . min ( prefixMin , prefixSum [ 0 ] ) ; for ( let i = 1 ; i < n ; i ++ ) { prefixSum [ i ] = prefixSum [ i - 1 ] + arr [ i ] ; prefixMin = Math . min ( prefixMin , prefixSum [ i ] ) ; } let countSubs = 0 ; mp . set ( 0 , 1 ) ; for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; prefixSum [ i ] - j * j >= prefixMin ; j ++ ) { if ( mp . has ( prefixSum [ i ] - j * j ) ) countSubs += mp . get ( prefixSum [ i ] - j * j ) ; } if ( mp . has ( prefixSum [ i ] ) ) { mp . set ( prefixSum [ i ] , mp . get ( prefixSum [ i ] ) + 1 ) ; } else { mp . set ( prefixSum [ i ] , 1 ) ; } } return countSubs ; } let arr = [ 2 , 3 , - 5 , 6 , - 7 , 4 ] ; let n = arr . length ; let ans = countSubarrays ( arr , n ) ; document . write ( ans ) ;