# minmizing average problem

Given a set containing N numbers, minimize the average where you can take out any string of consecutive numbers in the set. |N|<=100000

Ex. {5, 1, 7, 8, 2}

You can take out {1,7}, etc. but the way to minimize in this case is just to take out {7,8} which will give a minimum average of (5+2+1)/3=2.667.

NOTE:-You can't use the first or last one, so you can't take out {5} or {2}. I want to know the general procedure to minimize this. I am looking for a linear solution. thanks

• The note is extremely unclear Jun 23, 2014 at 9:30
• We are not allowed to take out first and last element from the set Jun 23, 2014 at 9:53
• So how is {1} considered the first or the last element in your example??? Jun 23, 2014 at 9:56
• Sry that was by mistake i correct that Jun 23, 2014 at 9:57
• OK, now it is unclear how {5,2} is considered a string of consecutive numbers!!! Jun 23, 2014 at 9:58

Build a $2$-dimensional table, with each cell $[i][j]$ indicating the sum of elements $i,i+1,\dots,j$:

n = array.length
table = array
for j = 1 to n-1:
table[j] = table[j-1]+array[j]
for i = 1 to n-1:
for j = i to n-1:
table[i][j] = table[i-1][j-1]-array[i]+array[j]


Then, find the indexes (other than first and last) of the cell with the largest value:

max = array
max_i = 1
max_j = 1
for i = 1 to n-2:
for j = i to n-2:
if max < table[i][j]:
max = table[i][j]
max_i = i
max_j = j
return max_i,max_j


Given a set of $n$ elements, time complexity and space complexity are both $O(n^2)$.

• supoose input contains {1,2,3,4,5} then table will look like similiar to this 1 3 6 10 15 ; 0 2 5 9 14 ; 0 0 3 7 12 ; 0 0 0 4 9 ; 0 0 0 0 5 then how it will proceed to the solution then Jun 23, 2014 at 10:50
• @user157920: he indexes of the cell with the largest value (indexes different than 0 and n-1, as dictated by the question at hand) would $$, representing the sum $2+3+4$. And that's the solution for your example. Jun 23, 2014 at 11:56
• Is this a general soln I mean is this applicable to all types of testcases Jun 23, 2014 at 12:15
• @user157920: Why don't you run test-cases and find out? Jun 23, 2014 at 12:16
• Ok i will thanks for the rply Jun 23, 2014 at 12:16

The average is minimized by taking only the smallest value in the set, i.e. take out the largest elements.

By the restriction of first/last element and consecutive string, you would take out the consecutive inner string which has the biggest weighted average (stringlength/n*stringaverage) and bigger than the weighted average of first and last element (2/n*firstlastaverage).

• but this requires to calculate the average of every possible combination of consecutive inner string so solution will have exponential complexity. This is a brute force technique , I am looking for a better solution Jun 23, 2014 at 10:49
• yes indeed; it is not entirely brute-force as you do not calculate the total average every time (just the string averages).you may think of some further restrictions on which inner strings to take, for example would not take any string containing "small" elements. Jun 23, 2014 at 10:54
• if n is of the order of 10^5 then it will take hours to resolve some of the test cases by this method as for calculating string average we need the string length for which we can have n-2-k+1Ck combinations for a substring of length k and k can vary from 1 to n-2 so not a god option to go with this I guess Jun 23, 2014 at 11:02
• yes but if you have nothing else.. Jun 23, 2014 at 11:04
• I am sure there exist some sublinear solution to this problem , I am working on it , or may be someone else can help me out Jun 23, 2014 at 11:07