Method name:
public static boolean equalSplit (int[] a)
if you can split an array to two and the total of the values are equal return true,example:
{-3,5,12,14,-9,13} // returns true -3 5 14 = 12 (-9) 13
{-3,5,-12,14,-9,13}; //return false,you can split it to two groups but the groups won`t be equal 3 5 14 (-12)=-9 13
{-3,5,12,14,-9}; // false because can`t split the array to two
Changing the array order is not allowed, recursion only no loops allowed, private methods are fine as long as recursive as well.
What i wrote(code not complete):
public class Rec
{
// private method to find total sum of an array.
static int findSum(int A[], int N)
{
if (N <= 0)
return 0;
return (findSum(A, N - 1) A[N - 1]);
}
//
public static boolean equalSplit (int[] a)
{
return(equalSplit(a,0,0));
}
// override
private static boolean equalSplit (int[] a,int sum,int i)
{
int totalSum = findSum(a,a.length); // total sum of the given array.
if(i > a.length) // run until reach the end of the array.
return false;
if(totalSum - sum == sum) // if subtracting the recursive sum from total sum gives equal number return true
return true;
int take = equalSplit(a,sum a[i] , i 1); // boolean cannot be convereted to int
}
}
What I'm trying to do: I used a private method to find the sum of the whole array, and subtract from the total sum. The sum in the main method that suppose to sum the array step by step. My problem is that the method is boolean and i have no idea how to use boolean method recursively to complete it.
My questions: Can you tell me if the structure is good? and how should I approach it?
CodePudding user response:
Here's a solution without using loops and not changing the orders,
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 futher 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
andarrB
.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.