Problem Statement
Xenia and Yvona have a new toy: a collection of wooden cubes. Each cube has a positive integer side length. They have a large enough supply of cubes of all possible sizes.
Both girls have decided to use exactly N cubes, placed on top of each other, to build a tower that would have height exactly H.
Calculate and return the largest possible positive difference between the volumes of their two towers.
Definition
- Class:
- CubeTower
- Method:
- difference
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long difference(int H, int N)
- (be sure your method is public)
Notes
- No weird cube placements allowed. The bottom cube in the tower is placed on the ground (so that its bottom face is horizontal), and each of the following cubes is placed onto the previous one so that the top face of the previous one and the bottom face of the current one touch and overlap partially.
- Watch out for integer overflow, the correct return value will sometimes overflow a 32-bit integer variable.
- The smallest cube has side = 1. It is not allowed to use cubes with side = 0.
Constraints
- H will be between 1 and 10^6, inclusive.
- N will be between 1 and H, inclusive.
Examples
4
2
Returns: 12
We want a tower of height 4 using exactly 2 cubes. There are three possible towers: start with a 3x3x3 cube and place a 1x1x1 cube on top of it start with a 2x2x2 cube and place another 2x2x2 cube on top of it start with a 1x1x1 cube and place a 3x3x3 cube on top of it The tower of the second kind has volume 8+8 = 16, the other two types of tower have volume 27+1 = 28. If one of the girls builds a tower of the second kind and the other girl a different tower, the difference between their volumes will be 28 - 16 = 12.17
16
Returns: 0
There are multiple different towers the girls may build but they all share the same total volume. (Each of those towers consists of fifteen 1x1x1 cubes and one 2x2x2 cube.)5
3
Returns: 12
9
3
Returns: 264