1

I need to find the average of two numbers using only an int as a data type. I cannot use the formula (x1+x2)/2 = mean because that would result in overflow if the numbers are large enough.

I found this formula 

int mid = low + ((high - low) / 2);

from this thread Explanation of the safe average of two numbers.

However, this formula does not work when negative numbers are involved. Does anyone have any ideas of how to go about solving this problem? Thanks

Edit - Java

Community
  • 1
  • 1
frillybob
  • 600
  • 2
  • 12
  • 26

4 Answers4

3

You say that you can't use the form μ=(x+y)/2, but that's basically the only way to calculate this that makes sense. You do bring up a good point about overflow, but all it takes is a bit of very basic algebra to find away around that. Remember the Distributive Property?

μ = (x + y) / 2 = x/2 + y/2

By dividing both integers by 2 before adding them, you mitigate the risk of overflowing. Try it with both values set to Integer.MAX_VALUE (though read the whole post first). So...

int avg(int x, int y) {
    return x/2 + y/2;
}

... should do it for you. Bear in mind, you're using ints exclusively? You're gonna have some precision issues to worry about when it comes to odd integers... for example, if you do avg(1, 1), you will get a result of 0. I'll leave accounting for and fixing that little problem to you, but this should get you on the right path.

nasukkin
  • 2,460
  • 1
  • 12
  • 19
  • I think the solution to solving the rounding issues with something like `if (temp1 % 2 != 0 && temp2 % 2 != 0) { avg += 1; }` – frillybob Aug 25 '16 at 19:44
  • @frillybob That's certainly one way to do it, for two numbers at least. – nasukkin Aug 25 '16 at 21:12
  • @nusukkin That way actually doesn't work all the time. These two numbers produce one number off with my above logic `-1073741823, 1073741824` Expected 0, actually 1 – frillybob Aug 25 '16 at 21:32
  • 1
    @frillybob how can you accept this answer with so many use cases where the result is totally wrong ? like avg(1,1) =0 how can you trust the results of this random approach? – Nicolas Filotto Aug 25 '16 at 21:55
  • @frillybob FYI modulus on negative number is a little bit tricky read this http://stackoverflow.com/questions/4403542/how-does-java-do-modulus-calculations-with-negative-numbers – Nicolas Filotto Aug 25 '16 at 22:10
  • @NicolasFilotto I had mentioned in my original answer that this was something he would have to consider in his final implementation. This was done in part to demonstrate that the classical implementation of mean can be implemented without running into collision problems. It was also done in part to ensure that I wasn't giving the whole solution to what appears to be a homework question. This gap in functionality which should be accounted for in the original implementation serves as an important lesson in how decimal truncation works when dealing with integers. – nasukkin Aug 25 '16 at 22:27
  • 2
    @nasukkin hidding behind the fact that it "appears to be a homework question" sounds too easy for me, propose a fully functionnal solution, you will then see that behind this approach you have many corner cases to cover which makes it much too error prone. – Nicolas Filotto Aug 26 '16 at 06:58
1

This should work for both negative and positive values as the bit for the sign is not shifted in this case:

// Convert the add operation as long to prevent overflow in case you use big
// integers
long total = (long) low + (long) high;
// Convert the mid value back to an int
int mid = (int) (total >> 1);

NB: This works if and only if low and high are both int which seems to be the case here according to your question.

Nicolas Filotto
  • 43,537
  • 11
  • 94
  • 122
  • Fails for very large and very small integers due to overflow. `>> 1` is equivalent to `/2`, so the problem that the question raised is still valid. Try with both values equal to `Integer.MAX_VALUE` or `Integer.MIN_VALUE`. – nasukkin Aug 25 '16 at 19:02
  • @nasukkin ok I see, please check again – Nicolas Filotto Aug 25 '16 at 19:12
  • 1
    This is probably the best answer... **if** the stipulation of "using only an int as a data type" from the original question allows for `long` to be used in the middle. However, if using long is acceptable, the bit-shift is unnecessary and should probably be replaced with `/ 2` for code readability. Actually, if using data-types other than `int` in the intermediate calculations is permitted, it's probably even better to use a floating-point data-type (such as BigDecimal). This would resolve some problems with decimal precision. – nasukkin Aug 25 '16 at 19:16
  • @nasukkin it is clearly mentioned in the question that the expected type is int – Nicolas Filotto Aug 25 '16 at 19:18
  • @nasukkin the answer is valid now, so please remove your down vote as your original remark is no more valid – Nicolas Filotto Aug 25 '16 at 19:29
0

Something like this should work

private int findAverage(int lower, int higher) {
    int lowerCopy = lower;
    int higherCopy = higher;
    boolean averageFound = false;
    while (!averageFound) {
        lowerCopy++;
        higherCopy--;
        averageFound = isAverageFound(lowerCopy, higherCopy);
    }
    return getAverage(lowerCopy, higherCopy);
}

Where isAverageFound would be implemented by checking if the values are either equal to one another or one away from one another.

This should work for all ranges of numbers, positive or negative

Brandon Laidig
  • 430
  • 2
  • 14
  • Consider the number of iterations that while loop would take for a very large negative number and a very large positive number. – Jonny Henly Aug 25 '16 at 18:33
  • For instance that while loop would iterate `100` times for `-100` and `100`. Now imagine the number of iterations for `Integer.MIN` and `Integer.MAX`. – Jonny Henly Aug 25 '16 at 18:41
-1
private void findAverage(int lower, int higher) {
    int lowerCopy = lower;
    int higherCopy = higher;
    int cnt = 1;
    boolean averageFound = false;
    while (!averageFound) {
        lowerCopy++;
        higherCopy--;
        ++cnt;
        averageFound = isAverageFound(lowerCopy, higherCopy);
    }
}


private boolean isAverageFound(int l, int h){
  if(l < h)
     return false;
   else if(l == h){
     System.out.print("average:" + l);
     return true;
   }else{
     System.out.print("average:" + (h/2));  
     return true;       
   }
}

Yes. It was left to change. And for the large negative and large positive range, it will work. However, i agree it will take O(high + low) time.

Darpan27
  • 239
  • 1
  • 4
  • 9