0

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

user157920
  • 109
  • 6

2 Answers2

1

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)$.

barak manos
  • 43,109
  • 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 – user157920 Jun 23 '14 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 $[1][3]$, representing the sum $2+3+4$. And that's the solution for your example. – barak manos Jun 23 '14 at 11:56
  • Is this a general soln I mean is this applicable to all types of testcases – user157920 Jun 23 '14 at 12:15
  • @user157920: Why don't you run test-cases and find out? – barak manos Jun 23 '14 at 12:16
  • Ok i will thanks for the rply – user157920 Jun 23 '14 at 12:16
  • @user157920: You're welcome. See updated answer for how to retrieve the indexes and find the solution. Also, please feel free to accept this answer (by clicking on the V next to it) if it works out for you. – barak manos Jun 23 '14 at 12:21
0

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).

emcor
  • 792
  • 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 – user157920 Jun 23 '14 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. – emcor Jun 23 '14 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 – user157920 Jun 23 '14 at 11:02
  • yes but if you have nothing else.. – emcor Jun 23 '14 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 – user157920 Jun 23 '14 at 11:07