Problem Statement
Captain Brown Beard keeps his pirate ship stocked with a healthy supply of cannon balls. Because he is very tidy, he insists that all of the cannon balls be stacked into perfect tetrahedron shapes. Such a pyramid is constructed by arranging cannon balls into an equilateral triangle with side length n. Then, on top of that is stacked an equilateral triangle of side length n-1, and so on, until there is a single cannon ball placed on the top (this single cannon ball is a triangle of side length 1). For example, a stack of size 3 will have three layers that look like this (from top to bottom):
X X X X X X X X X X
So, each triangle will contain 1, 3, 6, 10, etc. cannon balls. Thus, any complete stack will have 1, 4, 10, 20, etc. cannon balls.
You are given an
Definition
- Class:
- CannonBalls
- Method:
- fewestPiles
- Parameters:
- int
- Returns:
- int
- Method signature:
- int fewestPiles(int n)
- (be sure your method is public)
Constraints
- n will be between 1 and 300000, inclusive.
Examples
1
Returns: 1
This is the smallest single stack we can make.
5
Returns: 2
A stack with 1 cannon ball, and a stack with 4 cannon balls.
9
Returns: 3
9 = 4 + 4 + 1
15
Returns: 3
40
Returns: 2
91
Returns: 2
91 = 56 + 35
68296
Returns: 3
248308
Returns: 4
125494
Returns: 4
79764
Returns: 3
246972
Returns: 4
92798
Returns: 4
80472
Returns: 3
79490
Returns: 4
223820
Returns: 4
84176
Returns: 4
110567
Returns: 4
146520
Returns: 3
280787
Returns: 4
98910
Returns: 3
41829
Returns: 2
90581
Returns: 4
80548
Returns: 4
95725
Returns: 4
137134
Returns: 3
129416
Returns: 3
244306
Returns: 3
56192
Returns: 4
80968
Returns: 4
90204
Returns: 3
8059
Returns: 3
290687
Returns: 4
43576
Returns: 4
36753
Returns: 4
61262
Returns: 3
285975
Returns: 3
300000
Returns: 3
200000
Returns: 4
100000
Returns: 3
1000
Returns: 3
148437
Returns: 5
300000
Returns: 3
295240
Returns: 1
299998
Returns: 3
299997
Returns: 4
299999
Returns: 4
75
Returns: 3
83
Returns: 5