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
class Solution {
 public:
  int minimumBoxes(int n) {
    int nBoxes = 0;
    int nextTouchings = 0;   // j
    int currLevelBoxes = 0;  // 1 + 2 + ... + j

    // find min 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 we need to remove boxes in 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
class Solution {
  public int minimumBoxes(int n) {
    int nBoxes = 0;
    int nextTouchings = 0;  // j
    int currLevelBoxes = 0; // 1 + 2 + ... + j

    // find min 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 we need to remove boxes in 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
class Solution:
  def minimumBoxes(self, n: int) -> int:
    nBoxes = 0
    nextTouchings = 0   # j
    currLevelBoxes = 0  # 1 + 2 + ... + j

    # find min 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 we need to remove boxes in current level and rebuild it
    nBoxes -= currLevelBoxes
    currLevelBoxes -= nextTouchings
    nextTouchings = 0

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

    return currLevelBoxes + nextTouchings
Back to top