Summing Array Elements Using D&C algorithm gives wrong output

Viewed 28

can you please tell me what's wrong with this code. I tried to create a function that computes a sum of an array elements using D&C algorithm but always gives me wrong output.

public static long getSum(long arr[], int left, int right, long sum) {

    if (left<=right) {
        if (left==right) {

            return sum + arr[right];
        }
        int mid = (left + right) / 2;
        return  getSum(arr,  left+ 1, mid,sum + arr[left])  + getSum(arr, mid + 1, right, sum + arr[left]);
    }
    return 0;

public static void main(String[] args){
    long[] n = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int l = 0, r = n.length-1;
    long result = getSum(n,l,r,0);
    System.out.print(result);
1 Answers

arr[left] is added twice and this needs to be fixed so that the recursive call looks like:

...
return arr[left] + getSum(arr, left + 1, mid,   sum) 
                 + getSum(arr,  mid + 1, right, sum);

Also, it is possible to add an element at right index to the sum in the same line and decrement this index:

return arr[left]  + getSum(arr, left + 1, mid, sum) 
     + arr[right] + getSum(arr,  mid + 1, right - 1, sum);
Related