Skip to content

1739. Building Boxes 👍

  • Time: $O(n^{1/3})$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int minimumBoxes(int n) {
    int nBoxes = 0;
    int nextTouchings = 0;   // j
    int currLevelBoxes = 0;  // 1 + 2 + ... + j

    // Find the minimum j s.t. `nBoxes` = 1 + (1 + 2) + ... + (1 + 2 + ... + j)
    // >= n.
    while (nBoxes < n) {
      ++nextTouchings;
      currLevelBoxes += nextTouchings;
      nBoxes += currLevelBoxes;
    }

    // If nBoxes = n, the answer is `currLevelBoxes` = 1 + 2 + ... + j.
    if (nBoxes == n)
      return currLevelBoxes;

    // Otherwise, need to remove the boxes in the current level and rebuild it.
    nBoxes -= currLevelBoxes;
    currLevelBoxes -= nextTouchings;
    nextTouchings = 0;

    while (nBoxes < n) {
      ++nextTouchings;
      nBoxes += nextTouchings;
    }

    return currLevelBoxes + nextTouchings;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int minimumBoxes(int n) {
    int nBoxes = 0;
    int nextTouchings = 0;  // j
    int currLevelBoxes = 0; // 1 + 2 + ... + j

    // Find the minimum j s.t. `nBoxes` = 1 + (1 + 2) + ... + (1 + 2 + ... + j)
    // >= n.
    while (nBoxes < n) {
      ++nextTouchings;
      currLevelBoxes += nextTouchings;
      nBoxes += currLevelBoxes;
    }

    // If nBoxes = n, the answer is `currLevelBoxes` = 1 + 2 + ... + j.
    if (nBoxes == n)
      return currLevelBoxes;

    // Otherwise, need to remove the boxes in the current level and rebuild it.
    nBoxes -= currLevelBoxes;
    currLevelBoxes -= nextTouchings;
    nextTouchings = 0;

    while (nBoxes < n) {
      ++nextTouchings;
      nBoxes += nextTouchings;
    }

    return currLevelBoxes + nextTouchings;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def minimumBoxes(self, n: int) -> int:
    nBoxes = 0
    nextTouchings = 0  # j
    currLevelBoxes = 0  # 1 + 2 + ... + j

    # Find the minimum j s.t. `nBoxes` = 1 + (1 + 2) + ... + (1 + 2 + ... + j)
    # >= n
    while nBoxes < n:
      nextTouchings += 1
      currLevelBoxes += nextTouchings
      nBoxes += currLevelBoxes

    # If nBoxes = n, the answer is `currLevelBoxes` = 1 + 2 + ... + j.
    if nBoxes == n:
      return currLevelBoxes

    # Otherwise, need to remove the boxes in the current level and rebuild it.
    nBoxes -= currLevelBoxes
    currLevelBoxes -= nextTouchings
    nextTouchings = 0

    while nBoxes < n:
      nextTouchings += 1
      nBoxes += nextTouchings

    return currLevelBoxes + nextTouchings