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

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

2 Answers 2


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

n = array.length
table[0][0] = array[0]
for j = 1 to n-1:
    table[0][j] = table[0][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[1][1]
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)$.

  • $\begingroup$ 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 $\endgroup$
    – user157920
    Jun 23, 2014 at 10:50
  • $\begingroup$ @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 $[1][3]$, representing the sum $2+3+4$. And that's the solution for your example. $\endgroup$ Jun 23, 2014 at 11:56
  • $\begingroup$ Is this a general soln I mean is this applicable to all types of testcases $\endgroup$
    – user157920
    Jun 23, 2014 at 12:15
  • $\begingroup$ @user157920: Why don't you run test-cases and find out? $\endgroup$ Jun 23, 2014 at 12:16
  • $\begingroup$ Ok i will thanks for the rply $\endgroup$
    – user157920
    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).

  • $\begingroup$ 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 $\endgroup$
    – user157920
    Jun 23, 2014 at 10:49
  • $\begingroup$ 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. $\endgroup$
    – emcor
    Jun 23, 2014 at 10:54
  • $\begingroup$ 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 $\endgroup$
    – user157920
    Jun 23, 2014 at 11:02
  • $\begingroup$ yes but if you have nothing else.. $\endgroup$
    – emcor
    Jun 23, 2014 at 11:04
  • $\begingroup$ 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 $\endgroup$
    – user157920
    Jun 23, 2014 at 11:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .