I got a partition problem for which I need advice. I'm given a 1D array whose length is even. I need to write a boolean method to determine whether the array can be divided into 2 equally sized subarrays with equal sum, no loops are allowed.
For example, array #1 {-3,5,-12,14,-9,13} will return false, because -3 5 -12 14 = -9 13, however on the left side there are 4 elements and on the other side 2.
array #2 will return true: {-3,14,12,5,-9,13} : -3 5 14 = 12 - 9 13
Here's what I've done so far:
public static boolean canBeDividedEqually(int[] arr)
{
if (arr.length %2 ==0){
return canBeDividedEquallyHelper(arr, 0, 0, 0);
}
return false;
}
public static boolean canBeDividedEquallyHelper(int[] arr, int i, int sum1, int sum2)
{
if (i == arr.length){
return sum1 == sum2;}
return canBeDividedEquallyHelper(arr, i 1, sum1 arr[i], sum2) ||
canBeDividedEquallyHelper(arr, i 1, sum1, sum2 arr[i]);
}
For case #2, it will return true as expected, but for case #1 it will also return true. I need to add a condition that will disqualify an array of type case #1.
CodePudding user response：
You were almost there. In addition to the sums, pass the number of elements:
public class Solver
{
public static boolean canBeDividedEqually(int[] arr)
{
return canBeDividedEquallyHelper(arr, 0, 0, 0, 0, 0);
}
public static boolean canBeDividedEquallyHelper(int[] arr, int i, int nb1, int sum1, int nb2, int sum2)
{
if (i == arr.length)
return nb1 == nb2 && sum1 == sum2;
return canBeDividedEquallyHelper(arr, i 1, nb1 1, sum1 arr[i], nb2, sum2) ||
canBeDividedEquallyHelper(arr, i 1, nb1, sum1, nb2 1, sum2 arr[i]);
}
public static void main(String[] args)
{
System.out.println(canBeDividedEqually(new int[]{-3, 5, -12, 14, -9, 13})); // false
System.out.println(canBeDividedEqually(new int[]{-3, 14, 12, 5, -9, 13})); // true
}
}
CodePudding user response：
Try this.
static boolean canPartitioning(int[] arr) {
return new Object() {
int length = arr.length, half = length / 2;
boolean partition(int i, int selected, int sum, int rest) {
if (i >= length)
return selected == half && sum == rest;
return selected < half && partition(i 1, selected 1, sum arr[i], rest)
|| partition(i 1, selected, sum, rest arr[i]);
}
}.partition(0, 0, 0, 0);
}
public static void main(String[] args) {
System.out.println(canPartitioning(new int[] {-3, 5, -12, 14, -9, 13}));
System.out.println(canPartitioning(new int[] {-3, 14, 12, 5, -9, 13}));
}
output:
false
true
CodePudding user response：
Here's a solution without using loops,
static int[] arrA, arrB;
public static boolean equalSplit(int[] arr) {
//Step 1
if (arr.length % 2 == 0) {
int sumA = 0, sumB = 0; // Two int variables to store the value of sum.
// Initializing the two new arrays with equal length.
arrA = new int[arr.length / 2];
arrB = new int[arr.length / 2];
// Copying the elements from the given array to the new arrays.
arrA = createArray(arrA, 0, arr, 0);
arrB = createArray(arrB, 0, arr, arr.length / 2);
//Calculating and storing the sum in the variables.
sumA = arraySum(arrA, arrA.length);
sumB = arraySum(arrB, arrB.length);
return sumA == sumB; // Checking the codition
} else {
return false;
}
}
private static int[] createArray(int[] arr, int index, int[] copyFrom, int copyFromIndex) {
if(index == arr.length) return arr;
arr[index] = copyFrom[copyFromIndex];
index ;
copyFromIndex ;
return createArray(arr, index, copyFrom, copyFromIndex);
}
private static int arraySum(int[] arr, int N) {
if (N <= 0) return 0;
return (arraySum(arr, N - 1) arr[N - 1]);
}
My approach towards this question is,
Step 1 -> Checking whether can you split the given array into two equal arrays. If yes next comes the Step 2 or return false without any further steps.
Step 2 -> Copying the given array elements into two different but equal arrays using recursion.
Step 3 -> Sum the newly populated two arrays and store it in two different variable.
Step 4 -> If the Sum of both the newly populated arrays is equal then the function return true else false.
Explanation :
Create two new integer arrays which are going to get populated only if the given array can be divided into two equal parts. Here it is arrA and arrB.
Check whether if the length of given array can be divided by two and have 0 remainders because this can give the answer to the question "Can this array be divided into two equal parts ?". The piece of code in this answer is arr.length % 2 == 0. If the given array satisfies this condition only then the steps given below will be carried out else it will return false.
Initialize two integer variable to store the value of Sum of both the equally divided arrays.
Initialize the two newly created arrays with the array length of half the given array which is arr.length / 2.
Then copy first half of given array elements to the first newly initialized array then the second half to the second array. To achieve this createArray(int[] arr, int index, int[] copyFrom, int copyFromIndex) method is used. arr is the argument to pass the array which should be copied to, index should be 0 because it is used as the index of newly created arrays, copyFrom is a parameter for the given array which has all the elements, copyFromIndex is used to start copying the elements from the given index.
Then calculate the sum using recursive function and store it in separate variable which was created earlier. The function used here was arraySum(int[] arr, int N).
Return whether both the sum variables are equal.
CodePudding user response：
If the change of elements order is allowed, you have to check every possible permutation of the array:
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] a = {-3, 5, -12,14,-9,13};
int[] b = {-3,14, 12, 5,-9,13};
System.out.println(isEquallySplittable(a));
System.out.println(isEquallySplittable(b));
}
public static boolean isEquallySplittable(int[] array){
long arraySum = arraySum(array);
if(arraySum % 2 != 0) return false; //can not split an even sum by half
return isEquallySplittable(array, 0, 0, arraySum);
}
public static boolean isEquallySplittable(int[] array, int indexFrom, int indexTo, long sumArray){
if(indexTo == indexFrom) {
indexTo ;
}
if(indexTo >= array.length) {
indexTo = 0;
indexFrom ;
}
if(indexFrom >= array.length) return false;
long sumHalfArray = arraySum(Arrays.copyOf(array, array.length/2)); //sum first half of the array
if(sumArray == sumHalfArray * 2 ){
System.out.println(Arrays.toString(array) " can be split into 2 equal arrays");
return true;
}
//next permutation
int temp = array[indexTo];
array[indexTo] = array[indexFrom];
array[indexFrom] = temp;
return isEquallySplittable(array, indexFrom, indexTo, sumArray);
}
public static long arraySum(int[] arr) {
return arraySum(arr, 0, 0);
}
private static long arraySum(int[] arr, int index, long sum) {
if (index >= arr.length ) return sum;
sum = arr[index ];
return arraySum(arr,index,sum);
}
}