CODEWITHSUNDEEP
algorithm
user313
user313

Reputation: 699

How to find the x consecutive numbers with the highest average in a list?

So I came across this question earlier, and I'm stumped: When given a list of n integers, we are looking to return a value equal to the highest possible average of x consecutive integers in that list.

For example:

we have list [1, 2, 1, 7, 9, 8, 3, 2]

we have x = 3

our answer would be 8, because the sequence of 3 consecutive integers, with the highest average, is 7, 9, 8, and their average is 8.

[1, 2, 1, 7, 9, 8, 3, 2]

Anyone know how to approach this in code/pseudocode?

Upvotes: 0

Views: 841

Answers (2)

SomeDude
SomeDude

Reputation: 14238

Just have a sliding window of x and look for the maximum. The comments in the code should be self explanatory.

Note : Be careful while adding numbers they could be very large or your x is very high that you could run into overflow after adding numbers without dividing by x. So divide by x each time you add to sum.

double sum = 0;
for ( int i = 0; i < x; i++ ) {
   sum += (double) ( arr[i] ) / x; //calculate the average of first `x` numbers, if your input elements are integers you need to cast it to double.
}
double max = sum; //initialize a variable that has that value which you will maximize
for ( int i = x; i < n; i++ ) {
  sum -= (double)( arr[i-x] ) / x; //leave the first in the x elements
  sum += (double)( arr[i] ) / x; // add the current element so you always compute average of `x` elements.
  max = Math.max( max, sum ); //maximize max
}

return max;

Upvotes: 3

Kon
Kon

Reputation: 4099

You're looking for a sliding window average. Basically, you calculate the average for each of the possible sub-arrays of x length. You'd start with a window of indices 0 to (x-1), then go to 1 to x, then 2 to (x+1) and so on, calculating the average of each window. If the average of current window is greater than the average of previous window, you update your max average.

Upvotes: 2

Related Questions