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 boxy
, then each side of the four vertical sides of the boxy
must either be adjacent to another box or to a wall.
Given an integer n
, return the minimum possible number of boxes touching the floor.
Example 1:
Input: n = 3 Output: 3 Explanation: The figure above is for the placement of the three boxes. These boxes are placed in the corner of the room, where the corner is on the left side.
Example 2:
Input: n = 4 Output: 3 Explanation: The figure above is for the placement of the four boxes. These boxes are placed in the corner of the room, where the corner is on the left side.
Example 3:
Input: n = 10 Output: 6 Explanation: The figure above is for the placement of the ten boxes. These boxes are placed in the corner of the room, where the corner is on the back side.
Constraints:
1 <= n <= 109
Solution: Geometry
Step 1: Build a largest pyramid that has less then n cubes, whose base area is d*(d+1) / 2
Step 2: Build a largest triangle with cubes left, whose base area is l, l*(l + 1) / 2 >= left
Time complexity: O(n^(1/3))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int minimumBoxes(int n) { int d = 0; int l = 0; while (n - (d + 1) * (d + 2) / 2 > 0) { n -= (d + 1) * (d + 2) / 2; ++d; } while (n > 0) n -= ++l; return d * (d + 1) / 2 + l; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment