There is a problem with the divide and conquer algorithm for adding consecutive pairs of integers to an array
Therefore, I tried to understand the divide and conquer principle and multiple recursive calls in a single method. Everything works fine, but there is a problem with the output of the method I’m writing.
The purpose of the method is to return the sum of all consecutive pairs of numbers in an array. I’m 95% done, but not getting the output I was expecting, and I’ve been banging my head against tables for years trying to figure out why.
The array is:
int[] array = { 11, 6, 87, 32, 15, 5, 9, 21 };
The method is:
public int consecutivePairsSum_DivideAndConquer(int start, int end, int[] array) {
int leftSum;
int rightSum;
int middle = (start + end) / 2;
if (start == middle) {
return array[middle];
} else {
leftSum = array[start] + array[start + 1];
leftSum += consecutivePairsSum_DivideAndConquer(start, middle, array);
}
if (middle == end) {
return array[end];
} else {
rightSum = array[middle] + array[middle+1];
rightSum += consecutivePairsSum_DivideAndConquer(middle+1, end, array);
}
return leftSum + rightSum;
}
Here is my method call:
System.out.println(rF.consecutivePairsSum_DivideAndConquer(0, array.length-1, array));
I
think this must have something to do with the way I split the array, but not many experiments give me the right output.
Expected output: 340
Actual output: 330
Suggestions are welcome, it drives me crazy! :p
ps Any useful links to places where I can find reliable online tutorials/good books on recursion are also great (if that’s within the confines of SO to see how it doesn’t directly help solve programming problems).
Solution
The outline of the algorithm is as follows:
Basic case: If your array has fewer than two elements, the result is 0
(because there are no pairs).
Otherwise: divide the array in half and calculate the result of the left and right halves, then the result of the entire array is <result of left half> + <result of right half> + <last element of
left half> + <first element of right half>
. (Because the only missing pair here is the pair at the split position).
In Java, it would look like this:
int consPairSum(int[] array, int left, int right) {
if(right <= left + 1) return 0;
int mid = (left + right) / 2;
int leftPairSum = consPairSum(array, left, mid);
int rightPairSum = consPairSum(array, mid, right);
return leftPairSum + rightPairSum + array[mid - 1] + array[mid];
}
It should be called that
consPairSum(array, 0, array.length);