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 iint 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 Codeint 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 istatic 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 idef 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 Codeif __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 approachusing 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 istatic 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 ifunction 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> |
Output
3
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
