Count of subarrays whose sum is a perfect square | Python3 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
from collections import defaultdict NEW_LINE def countSubarrays ( arr , n ) : NEW_LINE INDENT mp = defaultdict ( lambda : 0 ) NEW_LINE prefixSum = [ 0 ] * n NEW_LINE prefixMin = 0 NEW_LINE prefixSum [ 0 ] = arr [ 0 ] NEW_LINE prefixMin = min ( prefixMin , prefixSum [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prefixSum [ i ] = prefixSum [ i - 1 ] + arr [ i ] NEW_LINE prefixMin = min ( prefixMin , prefixSum [ i ] ) NEW_LINE DEDENT countSubs = 0 NEW_LINE mp [ 0 ] = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT j = 0 NEW_LINE while prefixSum [ i ] - j * j >= prefixMin : NEW_LINE INDENT if prefixSum [ i ] - j * j in mp : NEW_LINE INDENT countSubs += mp [ prefixSum [ i ] - j * j ] NEW_LINE DEDENT j += 1 NEW_LINE DEDENT mp [ prefixSum [ i ] ] += 1 NEW_LINE DEDENT return countSubs NEW_LINE DEDENT arr = [ 2 , 3 , - 5 , 6 , - 7 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE ans = countSubarrays ( arr , n ) NEW_LINE print ( ans ) NEW_LINE