Wednesday, 10 October 2012

Average Without Overflow

Puzzle:

There are 10 numbers, each has values between 0 to 99. Write computer program to find the average of those 10 numbers, such that the total must never exceed 99 (at any point during or after iteration).

Answer:

/*
 * First Approach
 * Programming language: Java
 */
int[]number=new int[10];
// initialize number
int absolute_average=0,sum_of_remainders=0;
for(int i = 0 ; i < 10 ; ++i)
{ absolute_average+=number[i]/10;
  sum_of_remainders+=number[i]%10;
  if(sum_of_remainders>10)
  { absolute_average+=sum_of_remainders/10;
    /* or better:
    absolute_average+=1;
    (as sum_of_remainders cannot be more than 18 with this if-block in place.)
    */
    sum_of_remainders%=10;
  }
}
float average=absolute_average+(sum_of_remainders/10.0F);
// or :
//float average=((float)absolute_average)+(((float)sum_of_remainders)/10);

/*
 * Alternate Approach
 * Programming language: Java
 */
byte[]number=new byte[10];
// initialize number
double average=0.0;
for(int i = number.length ; --i > -1 ; )
  average+=number[i]/10.0;


Reason:

(x[1]+x[2]+.....+x[n])/n = (x[1]/n)+(x[2]/n)+.....+(x[n]/n)

Need for this puzzle:

Programming in similar way can be useful in preventing bit-overflow in a computer program.
More Explanation:
For example, int in Java can store a value between Integer.MIN_VALUE and Integer.MAX_VALUE, and any attempt to assign a number out of those bounds (which can happen during addition, subtraction, or multiplication) will result in bit-overflow and loss of precision. So is with byte(between Byte.MIN_VALUE and Byte.MAX_VALUE), short(between Short.MIN_VALUE and Short.MAX_VALUE), and long(between Long.MIN_VALUE and Long.MAX_VALUE).