Finding mean of array of ints

Question

Say you have an array of int (in any language with fixed size ints). How would you calculate the int closest to their mean?

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

Edit: This is not homework. I haven't had homework in five years. And this is my first time on stackoverflow, so please be nice!

Edit: The obvious approach of summing up and dividing may overflow, so I'm trying to think of an approach that is overflow safe, for both large arrays and large ints. I think handling overflow correctly (without cheating and using a different type) is by far the hardest part of this problem.

Answer 1

Here's a way that's fast, reasonably overflow-safe and can work when the number of elements isn't 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 sum by adding the numbers up, and dividing by the number of them, 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

note that this isn't very fast.