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 approachpublic 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 approachimport 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 Codelet 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!
