MinAvgTwoSlice

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

For example, array A such that:
    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

contains the following example slices:

        slice (1, 2), whose average is (2 + 2) / 2 = 2;
        slice (3, 4), whose average is (5 + 1) / 2 = 3;
        slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

The goal is to find the starting position of a slice whose average is minimal.

Write a function:

    int solution(vector<int> &A);

that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.

For example, given array A such that:
    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [2..100,000];
        each element of array A is an integer within the range [−10,000..10,000].

int solution(vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    vector<int> pre_sum(A.size());
    int pre_s = 0;

    for (size_t i = 0; i < A.size(); i++) {
        pre_s += A[i];
        pre_sum[i] = pre_s;
    }

    int start = 0;
    int end = 1;
    int min_start = start;
    double min_avg = double(pre_sum[end] - pre_sum[start] + A[start]) / (end - start + 1);

    for (size_t i = 1; i < A.size(); i++) {
        double avg = double(pre_sum[i] - pre_sum[start] + A[start]) / (i - start + 1);

        if (avg < min_avg) {
            min_avg = avg;
            min_start = start;
        }

        if (A[i] < min_avg) {
            start = i;
        }

    }

    return min_start;
}