c - Find the minimal average of any slice containing at least two elements in an array

Question

The full question is:Min Average Two Slice Codility

I don't understand why my code doesn't work.

I know the correct answer, but I can't find a contra example for my code:

struct partaverg {
    long double min;
    int slice;
};

long long sumfun(int arr[], int N) {
    int sum = 0;
    for (int i = 0; i < N; ++i)
        sum += arr[i];
    return sum;
}

int solution(int A[], int N) {
    long long sum;
    long double new_average;

    int left = 0;
    int right = N - 1;
    long double numofnum;
    long double leftaverg, rightaverg;
    sum = sumfun(A, N);
    struct partaverg result;
    new_average = result.min = sum / (long double)N;
    result.slice = 0;
    while (left + 1 < right) {
        numofnum = right - left;
        leftaverg = (sum - A[left]) / numofnum;
        rightaverg = (sum - A[right]) / numofnum;
        if (leftaverg > rightaverg) {
            sum -= A[right--];
            new_average = rightaverg;
        } else {
            sum -= A[left++];
            new_average = leftaverg;
        }
        if (result.min > new_average) {
            result.min=new_average;
            result.slice=left;
        }
    }
    return result.slice;
}

标签： c

Answer 1

当当前切片在最左边和最右边的位置保持相同的数字时，您的算法就会出现问题。你要删除哪个号码？左边还是右边？

您当前的算法总是删除左边的数字，但这可能是不正确的。考虑：

int arr[4] = {1,9, 10, 1 };

// left average = (1 + 9 + 10) /3
// right average = (9 + 10 + 1) /3

左平均值和右平均值相同，因此您的代码删除了左边的数字并继续处理这个切片：

{9, 10, 1 };

这是错误的。现在您无法再达到正确的结果，即：

{1,9};