Number of subarrays having sum of the form k ^ m , m >= 0 | JavaScript implementation of the above approach ; partial_sum ; Function to count number of sub - arrays whose sum is k ^ p where p >= 0 ; If m [ a + b ] = c , then add c to the current sum . ; Increase count of prefix sum . ; If m [ a + b ] = c , then add c to the current sum . ; Increase count of prefix sum . ; b = k ^ p , p >= 0 ; k ^ m can be maximum equal to 10 ^ 14. ; If m [ a + b ] = c , then add c to the current sum . ; Increase count of prefix sum . ; Driver code
let MAX = 100005 ; function partial_sum ( prefix_sum , arr , n ) { for ( let i = 1 ; i <= n ; i ++ ) { prefix_sum [ i ] = ( prefix_sum [ i - 1 ] + arr [ i - 1 ] ) ; } return prefix_sum ; } function countSubarrays ( arr , n , k ) { let prefix_sum = new Array ( MAX ) ; prefix_sum [ 0 ] = 0 ; prefix_sum = partial_sum ( prefix_sum , arr , n ) ; let sum ; if ( k == 1 ) { sum = 0 ; let m = new Map ( ) ; for ( let i = n ; i >= 0 ; i -- ) { if ( m . has ( prefix_sum [ i ] + 1 ) ) sum += m . get ( prefix_sum [ i ] + 1 ) ; if ( m . has ( prefix_sum [ i ] ) ) m . set ( prefix_sum [ i ] , m . get ( prefix_sum [ i ] ) + 1 ) ; else m . set ( prefix_sum [ i ] , 1 ) ; } return sum ; } if ( k == - 1 ) { sum = 0 ; let m = new Map ( ) ; for ( let i = n ; i >= 0 ; i -- ) { if ( m . has ( prefix_sum [ i ] + 1 ) ) sum += m . get ( prefix_sum [ i ] + 1 ) ; if ( m . has ( prefix_sum [ i ] - 1 ) ) sum += m . get ( prefix_sum [ i ] - 1 ) ; if ( m . has ( prefix_sum [ i ] ) ) m . set ( prefix_sum [ i ] , m . get ( prefix_sum [ i ] ) + 1 ) ; else m . set ( prefix_sum [ i ] , 1 ) ; } return sum ; } sum = 0 ; let b , l = 100000000000000 ; let m = new Map ( ) ; for ( let i = n ; i >= 0 ; i -- ) { b = 1 ; while ( true ) { if ( b > l ) break ; if ( m . has ( prefix_sum [ i ] + b ) ) sum += m . get ( prefix_sum [ i ] + b ) ; b *= k ; } if ( m . has ( prefix_sum [ i ] ) ) m . set ( ( prefix_sum [ i ] ) , m . get ( prefix_sum [ i ] ) + 1 ) ; else m . set ( ( prefix_sum [ i ] ) , 1 ) ; } return sum ; } let arr = [ 2 , 2 , 2 , 2 ] ; let n = arr . length ; let k = 2 ; document . write ( countSubarrays ( arr , n , k ) ) ;