Finding the average value of an ints array

Question

Let's say you have an int array (in any language with a fixed size of ints). How would you calculate the int closest to their value?

Edit: to be clear, the result does not have to be in the array. That is, for the input array [3, 6, 7], the expected result is 5. Also, I think we need to specify a specific rounding direction, so say rounding if you are equally close to two numbers.

Edit: This is not homework. Five years later, I did not have homework. And this is my first time in stackoverflow, so please be nice!

Edit: The obvious summation and division approach can overflow, so I'm trying to think of safe overflow for large arrays and large ints. I think that handling the overflow correctly (without cheating and using a different type) is by far the most difficult part of this problem.

Answer 1

Here's the way fast, reasonably overwhelming security can work when the number of elements is not known in advance.

// The length of someListOfNumbers doesn't need to be known in advance. int mean(SomeType someListOfNumbers) { double mean = 0, count = 0; foreach(element; someListOfNumbers) { count++; mean += (element - mean) / count; } if(count == 0) { throw new UserIsAnIdiotException( "Problem exists between keyboard and chair."); } return cast(int) floor(mean); } 

Answer 2

Calculate the amount by adding numbers up and dividing them by a number with rounding:

 mean = (int)((sum + length/2) / length; 

If you are worried about overflow, you can do something like:

 int mean = 0, remainder = 0 foreach n in number mean += n / length remainder += n % length if remainder > length mean += 1 remainder -= length if remainder > length/2 mean += 1 print "mean is: " mean 

Please note that this is not very fast.

Answer 3

um ... how about just calculating the average and then rounding to the integer? round(mean(thearray)) Most languages ​​have tools that allow you to specify a rounding method.

EDIT: So it turns out that this question really is to avoid overflow, not rounding. Let me make it clear that I agree with those who said (in the comments) that in practice there is nothing to worry about, since this happens so rarely, and when this happens, you can always avoid using a larger data type.

I see that several other people gave answers, which basically consist of dividing each number in the array by the number of arrays, and then adding them. This is also a good approach. But only for kicks, here's an alternative (in the C-ish pseudo-code):

 int sum_offset = 0; for (int i = 1; i < length(array); i++) sum_offset += array[i] - array[i-1]; // round by your method of choice int mean_offset = round((float)sum_offset / length(array)); int mean = mean_offset + array[0]; 

Or another way to do the same:

 int min = INT_MAX, max = INT_MIN; for (int i = 0; i < length(array); i++) { if (array[i] < min) min = array[i]; if (array[i] > max) max = array[i]; } int sum_offset = max - min; // round by your method of choice int mean_offset = round((float)sum_offset / length(array)); int mean = mean_offset + min; 

Of course, you need to make sure that sum_offset does not overflow, which can happen if the difference between the largest and smallest elements of the array is greater than INT_MAX. In this case, replace the last four lines with approximately the following:

 // round by your method of choice int mean_offset = round((float)max / length(array) - (float)min / length(array)); int mean = mean_offset + min; 

General information: this method or something like that works well for the mental calculation of the average array, the elements of which are grouped close to each other.

Answer 4

Guaranteed no overflow:

 length ← length of list average ← 0 for each result in the list do: average ← average + ( result / length ) end for 

This has significant accuracy issues if you use ints due to truncation (the average of six 4 turns out to be 0)

Answer 5

Welcome. fish, hope your stay will be enjoyable.

The following pseudo-code shows how to do this in the case when the amount will fit into the integer type and the round is rounded to the nearest integer.

In your example, the numbers add the sum to 16, dividing by 3 gives you 5 1/3, the number of rounds is up to 5.

 sum = 0 for i = 1 to array.size sum = sum + array[i] sum = sum / array.size sum = round (sum) 

Answer 6

Pseudocode for getting average :

 double mean = 0 int count = 0 foreach int number in numbers count++ mean += number - mean / count round(mean) // rounds up floor(mean + 0.5) // rounds up ceil(mean - 0.5) // rounds down 

Rounding usually involves adding 0.5, then truncating (gender), so round 3.5 to 4. If you want 3.5 to round to 3, do the rounding code yourself, but in the reverse order: subtract 0.5, then find the ceiling.

Edit: updated requirements (no overflow)

Answer 7

This pseudo-code finds the average and covers the overflow problem:

 double avg = 0 int count = 0 for x in array: count += 1 avg = avg * (count - 1) / count // readjust old average avg += x / count // add in new number 

After that you can apply your rounding code. If in your language there is no easy way to round, then something like this will work (rounded when more .5):

 int temp = avg - int(avg) // finds decimal portion if temp <= 0.5 avg = int(avg) // round down else avg = int(avg) + 1 // round up 

Answer 8

ARM assembly. =] Unsolicited. Do not overflow. Ever. (I hope so).

Perhaps you can optimize a bit. (Maybe use FP / LR?) = S Maybe THUMB will work better here.

 .arm ; r0 = pointer to array of integers ; r1 = number of integers in array ; returns mean in r0 mean: stmfd sp!, {r4,r5} mov r5, r1 mov r2, 0 ; sum_lo mov r3, 0 ; sum_hi cmp r1, 0 ; Check for empty array bz .end .loop: ldr r4, [r0], #4 add r2, r2, r4 adc r3, r3, #0 ; Handle overflow sub r1, r1, #1 ; Next bnz .loop .end: div r0, r2, r3, r5 ; Your own 64-bit/32-bit divide: r0 = (r3r2) / r5 bx lr