DWITE Online Computer Programming Contest, December 2010, Problem 2
Rectangles can be constructed out of smaller squares. Given a supply of unit squares ( in size), how many unique rectangles can be constructed?
The input will contain 5 lines, each an integer , the number of unit squares available.
The output will contain 5 lines, each a number of unique rectangles that can be constructed from up to unit squares (not all squares have to be used for some of the rectangles).
Note: a rectangle is unique if another rectangle that had previously been constructed can't be rotated to look the same way. That is, and are considered to be the same.
Sample Input
2
6
Sample Output
2
8
Problem Resource: DWITE
Comments
can someone help me make my code faster?
Try looking for patterns instead of iterating through all the numbers.
If you consider the input , for example, the next number with the same binary weight is , which is around a half billion iterations away.
Edit: As pointed out by sushi, is a billion, not a trillion.
Isn't around 1 billion? I'm sorry if I made a mistake.