Count ways to split an array into subarrays such that sum of the i | 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
function countOfWays ( arr , N ) { let pre = new Array ( N + 1 ) . fill ( 0 ) ; for ( let i = 0 ; i < N ; i ++ ) { pre [ i + 1 ] = pre [ i ] + arr [ i ] ; } let dp = new Array ( N + 2 ) . fill ( 0 ) . map ( ( ) => new Array ( N + 2 ) . fill ( 0 ) ) ; dp [ 1 ] [ 0 ] ++ ; let ans = 0 ; for ( let i = 0 ; i < N ; i ++ ) { for ( let 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 ; } let arr = [ 1 , 2 , 3 , 4 ] ; let N = arr . length ; document . write ( countOfWays ( arr , N ) ) ;