Question

1739. Building Boxes

中文文档

Description

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 y 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

Solutions

Solution 1: Mathematical Rule

According to the problem description, the box with the highest number of layers needs to be placed in the corner of the wall, and the arrangement of the boxes is in a step-like shape, which can minimize the number of boxes touching the ground.

Assume that the boxes are arranged in $k$ layers. From top to bottom, if each layer is filled, then the number of boxes in each layer is $1, 1+2, 1+2+3, \cdots, 1+2+\cdots+k$.

If there are still remaining boxes at this point, they can continue to be placed from the lowest layer. Assume that $i$ boxes are placed, then the cumulative number of boxes that can be placed is $1+2+\cdots+i$.

The time complexity is $O(\sqrt{n})$, where $n$ is the number of boxes given in the problem. The space complexity is $O(1)$.

class Solution:
  def minimumBoxes(self, n: int) -> int:
    s, k = 0, 1
    while s + k * (k + 1) // 2 <= n:
      s += k * (k + 1) // 2
      k += 1
    k -= 1
    ans = k * (k + 1) // 2
    k = 1
    while s < n:
      ans += 1
      s += k
      k += 1
    return ans

class Solution {
  public int minimumBoxes(int n) {
    int s = 0, k = 1;
    while (s + k * (k + 1) / 2 <= n) {
      s += k * (k + 1) / 2;
      ++k;
    }
    --k;
    int ans = k * (k + 1) / 2;
    k = 1;
    while (s < n) {
      ++ans;
      s += k;
      ++k;
    }
    return ans;
  }
}

class Solution {
public:
  int minimumBoxes(int n) {
    int s = 0, k = 1;
    while (s + k * (k + 1) / 2 <= n) {
      s += k * (k + 1) / 2;
      ++k;
    }
    --k;
    int ans = k * (k + 1) / 2;
    k = 1;
    while (s < n) {
      ++ans;
      s += k;
      ++k;
    }
    return ans;
  }
};

func minimumBoxes(n int) int {
  s, k := 0, 1
  for s+k*(k+1)/2 <= n {
    s += k * (k + 1) / 2
    k++
  }
  k--
  ans := k * (k + 1) / 2
  k = 1
  for s < n {
    ans++
    s += k
    k++
  }
  return ans
}