Java – There is a problem with the divide and conquer algorithm for adding consecutive pairs of integers to an array

There is a problem with the divide and conquer algorithm for adding consecutive pairs of integers to an array… here is a solution to the problem.

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);

Related Problems and Solutions