Problem Statement
A square cannonball pyramid of size S is an arrangement of cannonballs into S layers. The bottom layer is a square consisting of S*S cannonballs. The next layer is a square of (S-1)*(S-1) cannonballs, placed into the gaps between the cannonballs forming the bottom layer. And so on: each of the following layers is also a square, and in each layer the side of that square decreases by 1. The top layer consists of a single cannonball.
You have B cannonballs. Use all of them to build at most six perfect square cannonball pyramids. Return a int[] containing the sizes of those pyramids.
If there are multiple solutions, all will be accepted. If there is no solution, return an empty int[] instead.
Definition
- Class:
- CannonballPyramids
- Method:
- build
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] build(int B)
- (be sure your method is public)
Notes
- You do not have to minimize the number of pyramids built, any solution with at most six of them is valid.
- You must use all cannonballs you have.
Constraints
- B will be between 1 and 10^9, inclusive.
Examples
280
Returns: {7, 7 }A pyramid of size 7 has 7*7 + 6*6 + ... + 2*2 + 1*1 = 140 cannonballs. You can build two such pyramids.6
Returns: {1, 1, 1, 1, 1, 1 }You can build six pyramids of size 1 each. It's a valid solution, even though it does not use the smallest number of pyramids - that would be a pyramid of size 2 and a pyramid of size 1. (Also, it's the laziest solution, you do not have to stack any cannonballs at all, you just let them all lie on the floor.)1253620
Returns: {2, 9, 155 }Order of pyramids in the output does not matter. E.g., {9, 155, 2 } is also a valid answer.