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.