Number of subarrays having sum of the form k ^ m , m >= 0 | Java 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
import java . util . * ; class GFG { static final int MAX = 100005 ; static long [ ] partial_sum ( long [ ] prefix_sum , int [ ] arr , int n ) { for ( int i = 1 ; i <= n ; i ++ ) { prefix_sum [ i ] = ( prefix_sum [ i - 1 ] + arr [ i - 1 ] ) ; } return prefix_sum ; } static int countSubarrays ( int [ ] arr , int n , int k ) { long [ ] prefix_sum = new long [ MAX ] ; prefix_sum [ 0 ] = 0 ; prefix_sum = partial_sum ( prefix_sum , arr , n ) ; int sum ; if ( k == 1 ) { sum = 0 ; HashMap < Long , Integer > m = new HashMap < > ( ) ; for ( int i = n ; i >= 0 ; i -- ) { if ( m . containsKey ( prefix_sum [ i ] + 1 ) ) sum += m . get ( prefix_sum [ i ] + 1 ) ; if ( m . containsKey ( prefix_sum [ i ] ) ) m . put ( prefix_sum [ i ] , m . get ( prefix_sum [ i ] ) + 1 ) ; else m . put ( prefix_sum [ i ] , 1 ) ; } return sum ; } if ( k == - 1 ) { sum = 0 ; HashMap < Long , Integer > m = new HashMap < > ( ) ; for ( int i = n ; i >= 0 ; i -- ) { if ( m . containsKey ( prefix_sum [ i ] + 1 ) ) sum += m . get ( prefix_sum [ i ] + 1 ) ; if ( m . containsKey ( prefix_sum [ i ] - 1 ) ) sum += m . get ( prefix_sum [ i ] - 1 ) ; if ( m . containsKey ( prefix_sum [ i ] ) ) m . put ( prefix_sum [ i ] , m . get ( prefix_sum [ i ] ) + 1 ) ; else m . put ( prefix_sum [ i ] , 1 ) ; } return sum ; } sum = 0 ; long b , l = 100000000000000L ; HashMap < Long , Integer > m = new HashMap < > ( ) ; for ( int i = n ; i >= 0 ; i -- ) { b = 1 ; while ( true ) { if ( b > l ) break ; if ( m . containsKey ( prefix_sum [ i ] + b ) ) sum += m . get ( prefix_sum [ i ] + b ) ; b *= k ; } if ( m . containsKey ( prefix_sum [ i ] ) ) m . put ( ( prefix_sum [ i ] ) , m . get ( prefix_sum [ i ] ) + 1 ) ; else m . put ( ( prefix_sum [ i ] ) , 1 ) ; } return sum ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 2 , 2 , 2 } ; int n = arr . length ; int k = 2 ; System . out . print ( countSubarrays ( arr , n , k ) ) ; } }