Divide and conquer sum of array iterative

Issue

Is it possible to get the sum of an array using divide and conquer? I've tried it, but I always miss some numbers, or I calculate a number twice.

int[] arr = new int[]{1,2,3,4,5};

    public int sum(int[] arr) {
        int begin = 0;
        int end = array.length - 1;
        int counter = 0;

        while (begin <= end) {
            int mid = (begin + end) / 2;
            counter += arr[end] + arr[mid];
            end = mid - 1;
        }
        return counter;
    }

Solution

Of course, Diveide-and-conquer computation of the array's sum is possible. But I cannot see a UseCase for it? You're still computing at least the same amount of sums, you're still running into issues if the sum of arrayis greater than Integer.MAX_VALUE, ...

There is also no performance benefit like Codor showed in his answer to a related question.

Starting with Java 8 you can compute the sum in 1 line using streams.

int sum = Arrays.stream(array).sum();

The main flaw with your above code is the fact that you're only summing up index mid(2) and end(4). After that you skip to the lower bracket (index mid = 0 and end = 2). So you're missing index 3. This problem will become even more prevelant with larger arrays because you're skipping even more indices after the while's first iteration.

A quick Google search brought up this nice-looking talk about the general Divide-and-Conquer principle using a mechanism called Recursion. Maybe it can guide you to a working solution.

Answered By - Der_Reparator