Given an array arr[] consisting of N integers, the task is to find the number of ways to split the array into non-empty subarrays such that the sum of the ith subarray is divisible by i.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 3
Explanation:
Following are the number of ways to split the array into non-empty subarray as:
- Split the array into subarray as {1}, {2}, {3}, {4} and the sum of each of the ith subarray is divisible by i.
- Split the array into subarray as {1, 2, 3}, {4} and each of the ith subarray is divisible by i.
- Split the array into subarray as {1, 2, 3, 4} and each of the ith subarray is divisible by i.
As there are only 3 possible ways to split the given array. Therefore, print 3.
Input: arr[ ] = {1, 1, 1, 1, 1}
Output: 3
Approach: The given problem can be solved by using Dynamic Programming because it has overlapping subproblems and optimal substructure. The subproblems can be stored in dp[][] table using memoization where dp[i][j] stores the number of partitions till ith index of arr[] into j non-empty subarray. This idea can be implemented using the Prefix Sum array pre[] that store the sum of all elements till every ith index and dp[i][j] can be calculated as the sum of dp[k][j – 1] for all value of k < i such that (pre[i] – pre[k]) is a multiple of j. Follow the steps below to solve the given problem:
- Initialize a variable, say count that stores the number of possible splitting of the given array into subarray.
- Find the prefix sum of the array and store it in another array, say prefix[].
- Initialize a 2D array, say dp[][] that stores all the overlapping states dp[i][j].
- Iterate over the range [0, N] using the variable i and nested iterate over the range [N, 0] using the variable j and perform the following steps:
- Increment the value of dp[j + 1][pre[i + 1] % (j + 1)] by the value of dp[j][pre[i + 1] % j] as this denotes the count of partitions till index i into j continuous subsequence divisible by (j + 1).
- If the value of i is (N – 1), then update the value of count by dp[j][pre[i + 1] % j].
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; Â
// Function to count ways to split // an array into subarrays such that // sum of the i-th subarray is // divisible by i int countOfWays( int arr[], int N) { Â
    // Stores the prefix sum of array     int pre[N + 1] = { 0 };     for ( int i = 0; i < N; i++) { Â
        // Find the prefix sum         pre[i + 1] = pre[i] + arr[i];     } Â
    // Initialize dp[][] array     int dp[N + 1][N + 1];     memset (dp, 0, sizeof (dp));     dp[1][0]++; Â
    // Stores the count of splitting     int ans = 0; Â
    // Iterate over the range [0, N]     for ( int i = 0; i < N; i++) {         for ( int j = N; j >= 1; j--) { Â
            // Update the dp table             dp[j + 1][pre[i + 1] % (j + 1)]                 += dp[j][pre[i + 1] % j]; Â
            // If the last index is             // reached, then add it             // to the variable ans             if (i == N - 1) {                 ans += dp[j][pre[i + 1] % j];             }         }     } Â
    // Return the possible count of     // splitting of array into subarrays     return ans; } Â
// Driver Code int main() { Â Â Â Â int arr[] = { 1, 2, 3, 4 }; Â Â Â Â int N = sizeof (arr) / sizeof (arr[0]); Â
    cout << countOfWays(arr, N); Â
    return 0; } |
Java
// Java program for the above approach Â
public class GFG { Â Â Â Â Â Â
// Function to count ways to split // an array into subarrays such that // sum of the i-th subarray is // divisible by i static int countOfWays( int arr[], int N) { Â
    // Stores the prefix sum of array     int pre[] = new int [N + 1 ];          for ( int i = 0 ; i < N; i++) { Â
        // Find the prefix sum         pre[i + 1 ] = pre[i] + arr[i];     } Â
    // Initialize dp[][] array     int dp[][] = new int [N + 2 ][N + 2 ]; Â
    dp[ 1 ][ 0 ]++; Â
    // Stores the count of splitting     int ans = 0 ; Â
    // Iterate over the range [0, N]     for ( int i = 0 ; i < N; i++) {         for ( int j = N; j >= 1 ; j--) { Â
            // Update the dp table             dp[j + 1 ][pre[i + 1 ] % (j + 1 )]                 += dp[j][pre[i + 1 ] % j]; Â
            // If the last index is             // reached, then add it             // to the variable ans             if (i == N - 1 ) {                 ans += dp[j][pre[i + 1 ] % j];             }         }     } Â
    // Return the possible count of     // splitting of array into subarrays     return ans; } Â
    // Driver Code     public static void main (String[] args) {                      int arr[] = { 1 , 2 , 3 , 4 };             int N = arr.length;                      System.out.println(countOfWays(arr, N));     } } Â
// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach Â
import numpy as np Â
# Function to count ways to split # an array into subarrays such that # sum of the i-th subarray is # divisible by i def countOfWays(arr, N) : Â
    # Stores the prefix sum of array     pre = [ 0 ] * (N + 1 );          for i in range (N) : Â
        # Find the prefix sum         pre[i + 1 ] = pre[i] + arr[i]; Â
    # Initialize dp[][] array     dp = np.zeros((N + 2 ,N + 2 ));     dp[ 1 ][ 0 ] + = 1 ; Â
    # Stores the count of splitting     ans = 0 ; Â
    # Iterate over the range [0, N]     for i in range (N) :         for j in range (N, 0 , - 1 ) : Â
            # Update the dp table             dp[j + 1 ][pre[i + 1 ] % (j + 1 )] + = dp[j][pre[i + 1 ] % j]; Â
            # If the last index is             # reached, then add it             # to the variable ans             if (i = = N - 1 ) :                 ans + = dp[j][pre[i + 1 ] % j];                 # Return the possible count of     # splitting of array into subarrays     return ans; Â
Â
# Driver Code if __name__ = = Â "__main__" : Â
    arr = [ 1 , 2 , 3 , 4 ];     N = len (arr); Â
    print (countOfWays(arr, N));          # This code is contributed by AnkThon |
C#
// C# program for the above approach using System; Â
public class GFG { Â Â Â // Function to count ways to split // an array into subarrays such that // sum of the i-th subarray is // divisible by i static int countOfWays( int [] arr, int N) { Â
    // Stores the prefix sum of array     int [] pre = new int [N + 1];          for ( int i = 0; i < N; i++) { Â
        // Find the prefix sum         pre[i + 1] = pre[i] + arr[i];     } Â
    // Initialize dp[][] array     int [,] dp = new int [N + 2, N + 2]; Â
    dp[1, 0]++; Â
    // Stores the count of splitting     int ans = 0; Â
    // Iterate over the range [0, N]     for ( int i = 0; i < N; i++) {         for ( int j = N; j >= 1; j--) { Â
            // Update the dp table             dp[j + 1, pre[i + 1] % (j + 1)]                 += dp[j, pre[i + 1] % j]; Â
            // If the last index is             // reached, then add it             // to the variable ans             if (i == N - 1) {                 ans += dp[j, pre[i + 1] % j];             }         }     } Â
    // Return the possible count of     // splitting of array into subarrays     return ans; } Â
  // Driver Code   public static void Main(String []args) {          int [] arr = { 1, 2, 3, 4 };     int N = arr.Length;              Console.WriteLine(countOfWays(arr, N));   } Â
} Â
// This code is contributed by sanjoy_62. |
Javascript
<script> // Javascript 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 function countOfWays(arr, N) { Â
  // Stores the prefix sum of array   let pre = new Array(N + 1).fill(0); Â
  for (let i = 0; i < N; i++)   {        // Find the prefix sum     pre[i + 1] = pre[i] + arr[i];   } Â
  // Initialize dp[][] array   let dp = new Array(N + 2).fill(0).map(() => new Array(N + 2).fill(0)); Â
  dp[1][0]++; Â
  // Stores the count of splitting   let ans = 0; Â
  // Iterate over the range [0, N]   for (let i = 0; i < N; i++) {     for (let j = N; j >= 1; j--) {       // Update the dp table       dp[j + 1][pre[i + 1] % (j + 1)] += dp[j][pre[i + 1] % j]; Â
      // If the last index is       // reached, then add it       // to the variable ans       if (i == N - 1) {         ans += dp[j][pre[i + 1] % j];       }     }   } Â
  // Return the possible count of   // splitting of array into subarrays   return ans; } Â
// Driver Code Â
let arr = [1, 2, 3, 4]; let N = arr.length; Â
document.write(countOfWays(arr, N)); Â
// This code is contributed by _Saurabh_Jaiswal Â
</script> |
3
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!