You have a cubic storeroom where the width, length, and height of the room are all equal to n units. You are asked to place n boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:
You can place the boxes anywhere on the floor.
If box x is placed on top of the box y, then each side of the four vertical sides of the box ymust either be adjacent to another box or to a wall.
Given an integer n, return theminimum possible number of boxes touching the floor.
Input: n =3Output: 3Explanation: The figure above isfor the placement of the three boxes.These boxes are placed in the corner of the room, where the corner is on the left side.
Input: n =4Output: 3Explanation: The figure above isfor the placement of the four boxes.These boxes are placed in the corner of the room, where the corner is on the left side.
Input: n =10Output: 6Explanation: The figure above isfor the placement of the ten boxes.These boxes are placed in the corner of the room, where the corner is on the back side.
The problem is equivalent to stacking boxes in a corner to form a 3D pyramid. The minimum number of boxes touching the floor is the minimum base size such that the total number of boxes in the pyramid is at least n.
classSolution:
defminimumBoxes(self, n: int) -> int:
# Find the largest h such that h*(h+1)*(h+2)//6 <= n h =0while (h+1)*(h+2)*(h+3)//6<= n:
h +=1 used = h*(h+1)*(h+2)//6# Now, fill the remaining boxes on the floor res = h*(h+1)//2 left = n - used
if left ==0:
return res
# Add boxes one by one to the next row k =1while left >0:
res +=1 left -= k
k +=1return res
classSolution {
publicintminimumBoxes(int n) {
int h = 0;
while ((long)(h+1)*(h+2)*(h+3)/6 <= n) h++;
int used = h*(h+1)*(h+2)/6;
int res = h*(h+1)/2;
int left = n - used;
if (left == 0) return res;
int k = 1;
while (left > 0) {
res++;
left -= k++;
}
return res;
}
}
classSolution {
public:int minimumBoxes(int n) {
int h =0;
while ((longlong)(h+1)*(h+2)*(h+3)/6<= n) h++;
int used = h*(h+1)*(h+2)/6;
int res = h*(h+1)/2;
int left = n - used;
if (left ==0) return res;
int k =1;
while (left >0) {
res++;
left -= k++;
}
return res;
}
};
classSolution {
funminimumBoxes(n: Int): Int {
var h = 0while ((h+1).toLong()*(h+2)*(h+3)/6<= n) h++val used = h*(h+1)*(h+2)/6var res = h*(h+1)/2var left = n - used
if (left ==0) return res
var k = 1while (left > 0) {
res++ left -= k
k++ }
return res
}
}
impl Solution {
pubfnminimum_boxes(n: i32) -> i32 {
letmut h =0;
while (h+1)*(h+2)*(h+3)/6<= n {
h +=1;
}
let used = h*(h+1)*(h+2)/6;
letmut res = h*(h+1)/2;
letmut left = n - used;
if left ==0 {
return res;
}
letmut k =1;
while left >0 {
res +=1;
left -= k;
k +=1;
}
res
}
}