Given an array arr[] of size N, the task is to find the number of times the array can be partitioned repetitively into two subarrays such that the sum of the elements of both the subarrays is the same.
Examples:
Input: arr[] = { 2, 2, 2, 2 }
Output: 3
Explanation:
1. Make the first partition after index 1. Remaining arrays are {2, 2} on the right side and left side both.
2. Consider the left subarray {2, 2}. Make a partition after index 0 of this left subarray.
Now two similar subarrays with one element each i.e. {2} are formed which cannot be sub-divided.
3. Consider the right subarray {2, 2}. Make a partition after index 0 of this left subarray.
Now two similar subarrays with one element each i.e. {2} are formed which cannot be sub-divided.
Hence the output is 3 as the array was partitioned 3 times.Input: arr[] = {12, 3, 3, 0, 3, 3}
Output: 4
Explanation:
1. The first partition is after index 0. Remaining array is arr[] = {3, 3, 0, 3, 3}.
2. The second partition is after index 1. The remaining array is {3, 3}, and {0, 3, 3}.
3. The third partition is after index 0 in array {3, 3}.
4. The fourth partition is after 1 in the array {0, 3, 3}
The remaining array is {0, 3}, and {3} which cannot be sub-divided.
Hence the output is 4.
Approach: The idea is to use Recursion. Below are the steps:
- Find the prefix-sum of the given array arr[] and store it in an array pref[].
- Iterate from the start position to the end position.
- For each possible partition index(say K), if prefix_sum[K] – prefix_sum[start-1] = prefix_sum[end] – prefix_sum[k] then the partition is valid.
- If a partition is valid in the above step then proceed with the left and right sub-arrays separately and determine whether these two subarrays form a valid partition or not.
- Repeat the step 3 and 4 for both the left and right partition until any further partition isn’t possible.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Recursion Function to calculate the// possible splittingint splitArray(int start, int end, int* arr, int* prefix_sum){ // If there are less than // two elements, we cannot // partition the sub-array. if (start >= end) return 0; // Iterate from the start // to end-1. for (int k = start; k < end; ++k) { if ((prefix_sum[k] - prefix_sum[start - 1]) == (prefix_sum[end] - prefix_sum[k])) { // Recursive call to the left // and the right sub-array. return 1 + splitArray(start, k, arr, prefix_sum) + splitArray(k + 1, end, arr, prefix_sum); } } // If there is no such partition, // then return 0 return 0;}// Function to find the total splittingvoid solve(int arr[], int n){ // Prefix array to store // the prefix-sum using // 1 based indexing int prefix_sum[n + 1]; prefix_sum[0] = 0; // Store the prefix-sum for (int i = 1; i <= n; ++i) { prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]; } // Function Call to count the // number of splitting cout << splitArray(1, n, arr, prefix_sum);}// Driver Codeint main(){ // Given array int arr[] = { 12, 3, 3, 0, 3, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call solve(arr, N); return 0;} |
Java
// Java program for the above approachclass GFG{// Recursion Function to calculate the// possible splittingstatic int splitArray(int start, int end, int[] arr, int[] prefix_sum){ // If there are less than // two elements, we cannot // partition the sub-array. if (start >= end) return 0; // Iterate from the start // to end-1. for (int k = start; k < end; ++k) { if ((prefix_sum[k] - prefix_sum[start - 1]) == (prefix_sum[end] - prefix_sum[k])) { // Recursive call to the left // and the right sub-array. return 1 + splitArray(start, k, arr, prefix_sum) + splitArray(k + 1, end, arr, prefix_sum); } } // If there is no such partition, // then return 0 return 0;}// Function to find the total splittingstatic void solve(int arr[], int n){ // Prefix array to store // the prefix-sum using // 1 based indexing int []prefix_sum = new int[n + 1]; prefix_sum[0] = 0; // Store the prefix-sum for (int i = 1; i <= n; ++i) { prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]; } // Function Call to count the // number of splitting System.out.print(splitArray(1, n, arr, prefix_sum));}// Driver Codepublic static void main(String[] args){ // Given array int arr[] = { 12, 3, 3, 0, 3, 3 }; int N = arr.length; // Function call solve(arr, N);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Recursion Function to calculate the# possible splittingdef splitArray(start, end, arr, prefix_sum): # If there are less than # two elements, we cannot # partition the sub-array. if (start >= end): return 0 # Iterate from the start # to end-1. for k in range(start, end): if ((prefix_sum[k] - prefix_sum[start - 1]) == (prefix_sum[end] - prefix_sum[k])) : # Recursive call to the left # and the right sub-array. return (1 + splitArray(start, k, arr, prefix_sum) + splitArray(k + 1, end, arr, prefix_sum)) # If there is no such partition, # then return 0 return 0# Function to find the total splittingdef solve(arr, n): # Prefix array to store # the prefix-sum using # 1 based indexing prefix_sum = [0] * (n + 1) prefix_sum[0] = 0 # Store the prefix-sum for i in range(1, n + 1): prefix_sum[i] = (prefix_sum[i - 1] + arr[i - 1]) # Function Call to count the # number of splitting print(splitArray(1, n, arr, prefix_sum))# Driver Code# Given arrayarr = [ 12, 3, 3, 0, 3, 3 ]N = len(arr)# Function callsolve(arr, N)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{// Recursion Function to calculate the// possible splittingstatic int splitArray(int start, int end, int[] arr, int[] prefix_sum){ // If there are less than // two elements, we cannot // partition the sub-array. if (start >= end) return 0; // Iterate from the start // to end-1. for(int k = start; k < end; ++k) { if ((prefix_sum[k] - prefix_sum[start - 1]) == (prefix_sum[end] - prefix_sum[k])) { // Recursive call to the left // and the right sub-array. return 1 + splitArray(start, k, arr, prefix_sum) + splitArray(k + 1, end, arr, prefix_sum); } } // If there is no such partition, // then return 0 return 0;}// Function to find the total splittingstatic void solve(int []arr, int n){ // Prefix array to store // the prefix-sum using // 1 based indexing int []prefix_sum = new int[n + 1]; prefix_sum[0] = 0; // Store the prefix-sum for(int i = 1; i <= n; ++i) { prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]; } // Function Call to count the // number of splitting Console.Write(splitArray(1, n, arr, prefix_sum));}// Driver Codepublic static void Main(String[] args){ // Given array int []arr = { 12, 3, 3, 0, 3, 3 }; int N = arr.Length; // Function call solve(arr, N);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program to implement// the above approach// Recursion Function to calculate the// possible splittingfunction splitArray(start, end, arr, prefix_sum){ // If there are less than // two elements, we cannot // partition the sub-array. if (start >= end) return 0; // Iterate from the start // to end-1. for (let k = start; k < end; ++k) { if ((prefix_sum[k] - prefix_sum[start - 1]) == (prefix_sum[end] - prefix_sum[k])) { // Recursive call to the left // and the right sub-array. return 1 + splitArray(start, k, arr, prefix_sum) + splitArray(k + 1, end, arr, prefix_sum); } } // If there is no such partition, // then return 0 return 0;} // Function to find the total splittingfunction solve(arr, n){ // Prefix array to store // the prefix-sum using // 1 based indexing let prefix_sum = Array.from({length: n+1}, (_, i) => 0); prefix_sum[0] = 0; // Store the prefix-sum for (let i = 1; i <= n; ++i) { prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]; } // Function Call to count the // number of splitting document.write(splitArray(1, n, arr, prefix_sum));}// Driver code // Given array let arr = [ 12, 3, 3, 0, 3, 3 ]; let N = arr.length; // Function call solve(arr, N);// This code is contributed by code_hunt.</script> |
Output:
4
Time Complexity: O(N2)
Auxiliary Space: O(N)
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!
