Number of subarrays having sum of the form k ^ m , m >= 0 | C ++ implementation of the above approach ; 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
#include <bits/stdc++.h> NEW_LINE #define ll  long long NEW_LINE #define MAX  100005 NEW_LINE using namespace std ; ll countSubarrays ( int * arr , int n , int k ) { ll prefix_sum [ MAX ] ; prefix_sum [ 0 ] = 0 ; partial_sum ( arr , arr + n , prefix_sum + 1 ) ; ll sum ; if ( k == 1 ) { sum = 0 ; map < ll , int > m ; for ( int i = n ; i >= 0 ; i -- ) { if ( m . find ( prefix_sum [ i ] + 1 ) != m . end ( ) ) sum += m [ prefix_sum [ i ] + 1 ] ; m [ prefix_sum [ i ] ] ++ ; } return sum ; } if ( k == -1 ) { sum = 0 ; map < ll , int > m ; for ( int i = n ; i >= 0 ; i -- ) { if ( m . find ( prefix_sum [ i ] + 1 ) != m . end ( ) ) sum += m [ prefix_sum [ i ] + 1 ] ; if ( m . find ( prefix_sum [ i ] - 1 ) != m . end ( ) ) sum += m [ prefix_sum [ i ] - 1 ] ; m [ prefix_sum [ i ] ] ++ ; } return sum ; } sum = 0 ; ll b ; map < ll , int > m ; for ( int i = n ; i >= 0 ; i -- ) { b = 1 ; while ( true ) { if ( b > 100000000000000 ) break ; if ( m . find ( prefix_sum [ i ] + b ) != m . end ( ) ) sum += m [ prefix_sum [ i ] + b ] ; b *= k ; } m [ prefix_sum [ i ] ] ++ ; } return sum ; } int main ( ) { int arr [ ] = { 2 , 2 , 2 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 2 ; cout << countSubarrays ( arr , n , k ) ; return 0 ; }