CODEWITHSUNDEEP
javaarraysrecursiondivide-and-conquer
PumpkinBreath
PumpkinBreath

Reputation: 915

Having trouble with divide and conquer algorithm for adding consecutive pairs of ints in an array

So I am attempting to get my head around the divide and conquer principle and multiple recursive calls in a single method. It's going ok but I have a problem with the output of the method I am writing.

The purpose of the method is to return the sum of all the pairs of consecutive numbers in an array. I am 95% there but am not getting the output I expect and have been banging me head against the desk for ages trying to work out why.

The array is: 

int[] array = { 11, 6, 87, 32, 15, 5, 9, 21 };

and 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's my method call:

System.out.println(rF.consecutivePairsSum_DivideAndConquer(0, array.length-1, array));

I think it must be something to do with how I have split the array but no amount of experimenting is giving me the right output.

Expected output: 340

Actual output: 330

Any suggestions most welcome, this is driving me nuts! :p

ps Any useful links to where I can find a solid online tutorial/good book about recursion would also be great (if that's within the scope of SO seeing how it's not direct help with a programming issue)

Upvotes: 3

Views: 1452

Answers (2)

Sufian Latif
Sufian Latif

Reputation: 13356

Here's an outline of the algorithm:

Base case: If your array has less than two elements, the result is 0 (because there are no pairs).

Otherwise: Divide the array into two halves, calculate the results for left and right halves, then the result for the whole array would be <result of left half> + <result of right half> + <last element of left half> + <first element of right half> (Because the only pair missing here is the pair at the location of the split).

In java, it would be something 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 as

consPairSum(array, 0, array.length);

Upvotes: 2

mavriksc
mavriksc

Reputation: 1132

who said divide and conquer needs to divide into equal chunks you just need to divide into self similar problem. almost 1 liner. 

static private int doTheThing(int[] list){
    if (list.length==2)
        return list[0]+list[1];
    return list[0]+list[1]+doTheThing(Arrays.copyOfRange(list,1,list.length));
}

Upvotes: 1

Related Questions