Before we dive into the basic of computing average and give the answer as ((a+b)/2)), then I hate to say that, this will not work. Lets deep dive into basics first.
The value of Integer.MAX_VALUE = 2147483647. Now what will happen if we increment it with value 1. The answer is surprisingly -2147483648, which is also the value of Integer.MIN_VALUE.
So basically Integer.MAX_VALUE + 1 = Integer.MIN_VALUE
This is called overflow in java.
Before this we must understand how integer values are represented in binary form, and how binary addition works. Java uses a representation called two’s complement, in which the first bit of the number represents its sign. Whenever you add 1 to the largest java Integer, which has a bit sign of 0(Zero), then its bit sign becomes 1 and the number becomes negative. If an integer addition overflows, then the result is the low-order bits of the mathematical sum as represented in some sufficiently large two’s-complement format. If overflow occurs, then the sign of the result is not the same as the sign of the mathematical sum of the two operand values. Lets have a deeper look.
Before moving forward, lets step back and discuss what is two’s complement.
What is twos complement?
Two’s complement is a way of representing negative numbers in binary. Java uses this system to store negative numbers. The way it is done is, you flip all the bits and add one to it. So twos compliment of 0000 0001 is
1111 1110 + 1 =1111 1111
In the table below, if you take any positive 32 bit integer, flip the bits and add 1, you will get the binary representation of its negative value.
This can be verified in java through below code.
// gives you binary representation of -1
System.out.println(Integer.toBinaryString(-1));
//This will print 11111111111111111111111111111111However if you are interested in more detailed explanations, please have a look at this link.
Representing Integers in Java
Java uses two’s complement to represent the various forms of integers, with different numbers of bits for the different forms. A byte has eight bits, a short sixteen, an int thirty-two, and a long sixty-four. Why does Java use two's complement? Because it provides the advantage that addition is simple (you can use the standard algorithm for positive and negative numbers), subtraction is simple (subtraction can be implemented as negate and add), and because you can easily tell the sign of a number (if the leftmost bit is 0(Zero), the number is non-negative; if the leftmost bit is 1, the number is negative).
Now, why do we get a negative number when we add to the largest value in each? Let’s consider the largest integer, 01111111111111111111111111111111. All addition is done using the simple additional algorithm. Let's consider what happens when we add 2.
111111111111111111111111111111 (carry)
01111111111111111111111111111111
+ 10
---------------------------------
10000000000000000000000000000001What number is that? Well, we know it’s negative because it starts with a 1. Hence, we flip all the bits and then add 1 to find the corresponding positive number.
01111111111111111111111111111110
+ 1
------------------------------------
01111111111111111111111111111111So, in this notation, 231 + 2 = -231
The built-in integer operators do not indicate overflow or underflow in any way. Integer operators can throw a
NullPointerExceptionif unboxing conversion (§5.1.8) of a null reference is required. Other than that, the only integer operators that can throw an exception (§11) are the integer divide operator/(§15.17.2) and the integer remainder operator%(§15.17.3), which throw anArithmeticExceptionif the right-hand operand is zero, and the increment and decrement operators++(§15.15.1, §15.15.2) and--(§15.14.3, §15.14.2), which can throw anOutOfMemoryErrorif boxing conversion (§5.1.7) is required and there is not sufficient memory available to perform the conversion.
I think by now its clear what is happening behind the scene. Lets jump back to our question, which is “Find the average of Integer.MAX_VALUE in int.”
Lets discuss the very first solution which comes to our mind, i.e
Approach 1:
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;static int computeAverage(int a, int b) {
return (((a+b)/2));
}// Output is -1
// Expected: 2147483647
I think its very clear now why it is giving -1, because of overflow in this piece of code which is (a+b).
Approach 2:
Lets think different, the other solution which might come to our mind, is why not divide each value by 2, then add them together. Lets see what happens then. Below is the code.
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;static int computeAverage(int a, int b) {
return ((a/2) + (b/2));
}// Output is 2147483646
// Expected: 2147483647
Well, what happened in this solution. Lets try to understand this with a small number, say 5.
int d = 5;
int result = ((5/2) + (5/2));
System.out.println(result);// Output is 4
// Expected : 5/**
* Its the basic java that int c = 5/2;, it will print 2 instead of
* 2.5, and hence the result is 4 instead of 5.
*
* Similar is the case with int a = Integer.MAX_VALUE;
* a/2 will print 1073741823, instead of 1073741823.5.
* Hence, the final Output is 1 less than the expected output.
*/
So, above solution will be helpful if the value is even. For Example:
int a = Integer.MAX_VALUE - 1;
int b = Integer.MAX_VALUE - 1;static int computeAverage(int a, int b) {
return ((a/2) + (b/2));
}// Output is 2147483646
// Expected: 2147483647
Lets get back to our problem, till now Approach 1 and Approach 2 didn’t worked. Approach 2 will work only on the even number, but lets try to find a perfect solution which will work for both.
Approach 3:
If we look closely in Approach 2, our Output is 1 less that the Expected Value. So, why not just add 1 at the end. Well, this might works, but lets not do that for now. In order to get the value 1, we will perform the below operation:
((a % 2 + b % 2) / 2); // This will give the value 1./**
* Lets take our old number 5, int a = 5 % 2;, the result will be 1.
* Similarly, int a = Integer.MAX_VALUE % 2, the result will be 1.
* So, using this method we get the value as 1.
* */
Now, just add this method to our Approach 2, the final method will be:
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
static int compute_average(int a, int b) {
return (a / 2) + (b / 2) + ((a % 2 + b % 2) / 2);
}// Output is 2147483647
// Expected: 2147483647
Now since we got the solution, let’s try different approach. Let’s get back to basic first, by taking few examples:
1. What is the average of 6 and 6. Answer is 6.
2. What is the average of 80 and 80. Answer is 80.
3. What is the average of 8064 and 8064. Answer is 8064.
What we see in the above example, if we have to find the average of 2 same number, then the answer is that number itself. So, instead of that additional computation, what if provide a check if the number is same or not.
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
static int compute_average(int a, int b) {
if(a == b) return a;
return (a / 2) + (b / 2) + ((a % 2 + b % 2) / 2);
}This is the complete solution. BTW, this was the question which was asked in PayPal.
Hope I was able to make you understand what is going on behind the scenes.
Happy Coding !.
