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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define lli  long long int NEW_LINE lli countSubarrays ( int arr [ ] , int n ) { unordered_map < int , int > mp ; int prefixSum [ n ] ; int prefixMin = 0 ; prefixSum [ 0 ] = arr [ 0 ] ; prefixMin = min ( prefixMin , prefixSum [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { prefixSum [ i ] = prefixSum [ i - 1 ] + arr [ i ] ; prefixMin = min ( prefixMin , prefixSum [ i ] ) ; } lli countSubs = 0 ; mp [ 0 ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; prefixSum [ i ] - j * j >= prefixMin ; j ++ ) { if ( mp . find ( prefixSum [ i ] - j * j ) != mp . end ( ) ) countSubs += mp [ prefixSum [ i ] - j * j ] ; } mp [ prefixSum [ i ] ] ++ ; } return countSubs ; } int main ( ) { int arr [ ] = { 2 , 3 , -5 , 6 , -7 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; lli ans = countSubarrays ( arr , n ) ; cout << ans ; return 0 ; }