Given an integer K and an array arr[] of N integers, the task is to find the number of ways to split the array into K equal sum sub-arrays of non-zero lengths.
Examples:
Input: arr[] = {0, 0, 0, 0}, K = 3
Output: 3
All possible ways are:
{{0}, {0}, {0, 0}}
{{0}, {0, 0}, {0}}
{{0, 0}, {0}, {0}}
Input: arr[] = {1, -1, 1, -1}, K = 2
Output: 1
Approach: This problem can be solved using dynamic programming. Following will be our algorithm:
- Find the sum of all the elements of the array and store it in a variable SUM.
Before going to step 2, let’s try and understand the states of the DP.
For that, visualize putting bars to divide the array into K equal parts. So, we have to put K – 1 bar in total.
Thus, our states of dp will contain 2 terms.- i – index of the element we are currently upon.
- ck – number of bars we have already inserted + 1.
- Call a recursive function with i = 0 and ck = 1 and the recurrence relation will be:
Case 1: sum upto index i equals ((SUM)/k)* ck
dp[i][ck] = dp[i+1][ck] + dp[i+1][ck+1]
Case 2: sum upto index not i equals ((SUM)/k)* ck
dp[i][ck] = dp[i+1][ck]
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define max_size 20#define max_k 20using namespace std;// Array to store the states of DPint dp[max_size][max_k];// Array to check if a// state has been solved beforebool v[max_size][max_k];// To store the sum of// the array elementsint sum = 0;// Function to find the sum of// all the array elementsvoid findSum(int arr[], int n){ for (int i = 0; i < n; i++) sum += arr[i];}// Function to return the number of waysint cntWays(int arr[], int i, int ck, int k, int n, int curr_sum){ // If sum is not divisible by k // answer will be zero if (sum % k != 0) return 0; if (i != n and ck == k + 1) return 0; // Base case if (i == n) { if (ck == k + 1) return 1; else return 0; } // To check if a state // has been solved before if (v[i][ck]) return dp[i][ck]; // Sum of all the numbers from the beginning // of the array curr_sum += arr[i]; // Setting the current state as solved v[i][ck] = 1; // Recurrence relation dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum); if (curr_sum == (sum / k) * ck) dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum); // Returning solved state return dp[i][ck];}// Driver codeint main(){ int arr[] = { 1, -1, 1, -1, 1, -1 }; int n = sizeof(arr) / sizeof(int); int k = 2; // Function call to find the // sum of the array elements findSum(arr, n); // Print the number of ways cout << cntWays(arr, 0, 1, k, n, 0);} |
Java
// Java implementation of the approachclass GFG { static int max_size= 20;static int max_k =20;// Array to store the states of DPstatic int [][]dp = new int[max_size][max_k];// Array to check if a// state has been solved beforestatic boolean [][]v = new boolean[max_size][max_k];// To store the sum of// the array elementsstatic int sum = 0;// Function to find the sum of// all the array elementsstatic void findSum(int arr[], int n){ for (int i = 0; i < n; i++) sum += arr[i];}// Function to return the number of waysstatic int cntWays(int arr[], int i, int ck, int k, int n, int curr_sum){ // If sum is not divisible by k // answer will be zero if (sum % k != 0) return 0; if (i != n && ck == k + 1) return 0; // Base case if (i == n) { if (ck == k + 1) return 1; else return 0; } // To check if a state // has been solved before if (v[i][ck]) return dp[i][ck]; // Sum of all the numbers from the beginning // of the array curr_sum += arr[i]; // Setting the current state as solved v[i][ck] = true; // Recurrence relation dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum); if (curr_sum == (sum / k) * ck) dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum); // Returning solved state return dp[i][ck];}// Driver codepublic static void main(String[] args){ int arr[] = { 1, -1, 1, -1, 1, -1 }; int n = arr.length; int k = 2; // Function call to find the // sum of the array elements findSum(arr, n); // Print the number of ways System.out.println(cntWays(arr, 0, 1, k, n, 0));}}// This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approachimport numpy as npmax_size = 20max_k = 20# Array to store the states of DP dp = np.zeros((max_size,max_k)); # Array to check if a # state has been solved before v = np.zeros((max_size,max_k)); # To store the sum of # the array elements sum = 0; # Function to find the sum of # all the array elements def findSum(arr, n) : global sum for i in range(n) : sum += arr[i]; # Function to return the number of ways def cntWays(arr, i, ck, k, n, curr_sum) : # If sum is not divisible by k # answer will be zero if (sum % k != 0) : return 0; if (i != n and ck == k + 1) : return 0; # Base case if (i == n) : if (ck == k + 1) : return 1; else : return 0; # To check if a state # has been solved before if (v[i][ck]) : return dp[i][ck]; # Sum of all the numbers from the beginning # of the array curr_sum += arr[i]; # Setting the current state as solved v[i][ck] = 1; # Recurrence relation dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum); if (curr_sum == (sum / k) * ck) : dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum); # Returning solved state return dp[i][ck]; # Driver code if __name__ == "__main__" : arr = [ 1, -1, 1, -1, 1, -1 ]; n = len(arr); k = 2; # Function call to find the # sum of the array elements findSum(arr, n); # Print the number of ways print(cntWays(arr, 0, 1, k, n, 0)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG { static int max_size= 20;static int max_k =20;// Array to store the states of DPstatic int [,]dp = new int[max_size, max_k];// Array to check if a// state has been solved beforestatic Boolean [,]v = new Boolean[max_size, max_k];// To store the sum of// the array elementsstatic int sum = 0;// Function to find the sum of// all the array elementsstatic void findSum(int []arr, int n){ for (int i = 0; i < n; i++) sum += arr[i];}// Function to return the number of waysstatic int cntWays(int []arr, int i, int ck, int k, int n, int curr_sum){ // If sum is not divisible by k // answer will be zero if (sum % k != 0) return 0; if (i != n && ck == k + 1) return 0; // Base case if (i == n) { if (ck == k + 1) return 1; else return 0; } // To check if a state // has been solved before if (v[i, ck]) return dp[i, ck]; // Sum of all the numbers from the beginning // of the array curr_sum += arr[i]; // Setting the current state as solved v[i, ck] = true; // Recurrence relation dp[i,ck] = cntWays(arr, i + 1, ck, k, n, curr_sum); if (curr_sum == (sum / k) * ck) dp[i, ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum); // Returning solved state return dp[i, ck];}// Driver codepublic static void Main(String[] args){ int []arr = { 1, -1, 1, -1, 1, -1 }; int n = arr.Length; int k = 2; // Function call to find the // sum of the array elements findSum(arr, n); // Print the number of ways Console.WriteLine(cntWays(arr, 0, 1, k, n, 0));}}// This code contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approachvar max_size = 20;var max_k = 20// Array to store the states of DPvar dp = Array.from(Array(max_size), ()=> Array(max_k));// Array to check if a// state has been solved beforevar v = Array.from(Array(max_size), ()=> Array(max_k));// To store the sum of// the array elementsvar sum = 0;// Function to find the sum of// all the array elementsfunction findSum(arr, n){ for (var i = 0; i < n; i++) sum += arr[i];}// Function to return the number of waysfunction cntWays(arr, i, ck, k, n, curr_sum){ // If sum is not divisible by k // answer will be zero if (sum % k != 0) return 0; if (i != n && ck == k + 1) return 0; // Base case if (i == n) { if (ck == k + 1) return 1; else return 0; } // To check if a state // has been solved before if (v[i][ck]) return dp[i][ck]; // Sum of all the numbers from the beginning // of the array curr_sum += arr[i]; // Setting the current state as solved v[i][ck] = 1; // Recurrence relation dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum); if (curr_sum == (sum / k) * ck) dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum); // Returning solved state return dp[i][ck];}// Driver codevar arr = [1, -1, 1, -1, 1, -1];var n = arr.length;var k = 2;// Function call to find the// sum of the array elementsfindSum(arr, n);// Print the number of waysdocument.write( cntWays(arr, 0, 1, k, n, 0));</script> |
Output:
2
Time Complexity: O(n*k)
Auxiliary Space: O(n*k)
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!
