Count ways to split an array into subarrays such that sum of the i | Java program for the above approach ; Function to count ways to split an array into subarrays such that sum of the i - th subarray is divisible by i ; Stores the prefix sum of array ; Find the prefix sum ; Initialize dp [ ] [ ] array ; Stores the count of splitting ; Iterate over the range [ 0 , N ] ; Update the dp table ; If the last index is reached , then add it to the variable ans ; Return the possible count of splitting of array into subarrays ; Driver Code
public class GFG { static int countOfWays ( int arr [ ] , int N ) { int pre [ ] = new int [ N + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) { pre [ i + 1 ] = pre [ i ] + arr [ i ] ; } int dp [ ] [ ] = new int [ N + 2 ] [ N + 2 ] ; dp [ 1 ] [ 0 ] ++ ; int ans = 0 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = N ; j >= 1 ; j -- ) { dp [ j + 1 ] [ pre [ i + 1 ] % ( j + 1 ) ] += dp [ j ] [ pre [ i + 1 ] % j ] ; if ( i == N - 1 ) { ans += dp [ j ] [ pre [ i + 1 ] % j ] ; } } } return ans ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int N = arr . length ; System . out . println ( countOfWays ( arr , N ) ) ; } }