TopCoder BiggestRectangleEasy

This is an easy problem, but can be solved with short code using bit-wise binary operators, and as I'm always a big fan of binary tricks, I decided to post it here.

Problem Statement

Little Josh has found several sticks that are each 1 inch long. He wants to form a rectangle with the biggest possible area, using these sticks as the perimeter. He is allowed to glue sticks together, but he is not allowed to break a single stick into multiple shorter sticks. For example, if Josh has 11 sticks, he can create a 2 x 3 rectangle using 10 sticks. This rectangle has an area of 6 square inches, which is the biggest area that can be achieved in this case. You will be given an int N, and you must return the maximal area (in square inches) of a rectangle that can be created using N or less sticks.

so how can we solve this problem?

Let's see what we can do. First if the number of sticks is odd, we have to remove one stick as there can't be a rectangle with an odd perimeter. We have a rectangle with a perimeter N, and we all know that the perimeter of a rectangle is 2 * (rectangle's width + rectangle's height).

suppose width is "w" and height is "h", we divide by "2" to get sum = "w + h".

Now, we want to maximize "w * h" and we already have sum = "w + h".
one way to find "w" and "h" that maximize the product, is to try with "w" = 1 and h = "sum - 1" then store their product, then keep increasing "w" and decreasing "h" to find the values that will maximizes their product.

So this will give us a linear-time solution in terms of "w + h". A simple observation however, is that in order to maximize "w * h", "w" and "h' have to be as close as possible (I don't know a mathematical proof for that, if you know one please post it here". So, we simply set "w" = sum/2 and "h" = sum - w, and we have the maximum area that we can have with N sticks!.

Now let's see code for this.

int findArea(int N)
{
   // If the number of sticks is odd, remove one.
   // Divide by 2 to get "w+h"
   N >>= 1;
   // set "w" to "N/2"
   int w = N >> 1;
   // return "w * h"
   return (w * (N - w));
}