# 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