How to find if there's arithmatic mean of contiguous elements in a sorted array that equals to a given value in the most efficient running time?

Question

INPUT:

• Sorted array of positive, natural numbers,

EXPECTED COMPLEXITY:

• Time: O(n)
• Additional space: O(1)

Example:

Input:

arr = {2,3,17,30} x=10

Expected behavior:

The function prints the indexes : 1,2 and returns true since (3+17)/2 = x = 10

Input:

x = 30

Expected behavior:

The function will print the index 3 and return true since (30)/1 = x = 30`

My approach to the algorithm:

we will take the arithmatic mean starting with the first element in the array. If x is greater than our result we will add the next element in the array to the arithmatic mean.Else we will subtract the first element from the arithmatc mean.

I tried it and it didn't work. Can anyone help me?

Answer 1

1. Find the largest k, for which sum of a0+a1+a2+...+ak <= k*target
2. If sum == k*target - ok
3. If sum != k*target - add next element, and then subtract first elements until the average becomes smaller or equal than the target.

If your k reaches array length, no solution. Else you have the solution. Complexity O(n) as if step 3 you only add one number as previous sum + ak+1 was greater than k*target and you can only move left border only n times.

1. proc(array, x):
2.     sum = 0;
3.     left = 0;
4.     right = 0;
5.     do:
6.         sum += array[right];
7.         right++;
8.     while (sum+array[right] <= (right+1)*target && right<array.size);
9.     if (sum == right*target):
10.        for (i = left; i < right; i++):
11.            print(array[i] + <sep>);
12.        end_for
13.        return;
14.    end_if
15.    while (left <= right):
16.        if (right<array.size): sum += array[right++];
17.        do:
18.            sum-=array[left++]
19.        while (sum > target*(right-left));
20.        if (sum == target*(right-left)):
21.            for (i = left; i < right; i++):
22.                print(array[i] + <sep>);
23.            end_for
24.            return;
25.        end_if
26.    end_while
27.end_proc

Working properly for arrays with all numbers positive. Small modifications required for negatives but on interviews they often ask about arrays with all numbers positive. Some additional escape conditions might be needed in case there is no proper solution.

Answer 2

If we calculated the average of k elements from 0 to k, what we can tell about average from 1 to k, or about from 0 to k + 1? Both averages 1 to k and 0 to k + 1 are equal or greater to the average of first k elemnts. Why? Going from subset from 0 to k to subset from 1 to k, means removing the least element, so may not decrease total average. Going from subset from 0 to k to subset from 0 to k + 1, means adding an element which isn't smaller that every other, so it may not decrease total average.

Do we know which number from given array must be part of the result? Yes, this is the last smaller or equal to the target. Why? When it is equal, then we are done When it is not equal, then we need to have both bigger and lower elements.

Then, we maintain the average increasing it by adding elements from right side, and decreasing from left side.

public static int[] findMean(int[] input, int target) {
    int firstGreater = 0;
    int n = input.length;
    while(firstGreater < n && input[firstGreater] <= target) firstGreater++; // use binary search instead!
    if(firstGreater == 0 || firstGreater == n) return new int[]{-1,-1};
    int left = firstGreater - 1, right = firstGreater;
    long sum = input[left];
    while ((right < n &&(right - left) * target > sum) || (left > 0 && (right - left) * target < sum)) {
        if((right - left) * target > sum) sum += input[right++];
        else sum += input[--left];
    }
    if((right - left) * target != sum) {
        left = right = -1;
    }
    return new int[]{left, right - 1};
}