Parallel Average

import java.util.Arrays;

class Main {
    
    public static double reduce (int[] N) {
        
        if (N.length == 2) {
            return (double)(N[0] + N[1]) / 2;
        } else if (N.length == 3) {
            return (double)(N[0] + N[1] + N[2]) / 3;
        }
        
        int[] p1 = Arrays.copyOfRange(N, 0, N.length / 2);
        int[] p2 = Arrays.copyOfRange(N, N.length / 2, N.length);
        
        return (double)(reduce(p1) + reduce(p2)) / 2;
    }
    
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
        
        System.out.println(reduce(a));
    }
}

/*

so if you have a list like this:

[1, 2, 3, 4, 5, 6, 7, 8]

it goes

1. reduce([1, 2, 3, 4, 5, 6, 7, 8])
2. = reduce([1, 2, 3, 4]) + reduce([5, 6, 7, 8])
3. = (reduce([1, 2]) + reduce([3, 4])) + (reduce([5, 6]) + reduce([7, 8]))

so reduce() is called n - 1 times, but there are three steps
if each step could be computed in parallel, then this would run in O(logN) time

*/