Building Boxes
Asked at Adobe
Problem
With n unit cubes, build a house where every cube above the ground layer is supported by a cube directly beneath it, minimizing the number of cubes that touch the ground. This greedy-with-binary-search hard problem is a signature Adobe math question with n up to one billion.
Asked At
| Company | Difficulty | |
|---|---|---|
| Adobe | Hard | View all Adobe questions → |
How to Think About It
Brute force: for every candidate ground count, stack cubes upward and check capacity. Infeasible because n reaches 10^9 - you cannot simulate cube by cube. The answer must come from closed-form geometry.
Key insight: the most space-efficient building is a stair pyramid. A full pyramid whose base triangle has side s holds s(s+1)(s+2)/6 cubes total, of which s(s+1)/2 touch the ground.
First, binary search the largest s such that s(s+1)(s+2)/6 <= n. Those cubes are already supported. The leftover cubes must be added as a new bottom row extending the base triangle to side s+1.
The remainder rule: the j-th ground cube added to the extended triangle row brings j additional cube positions above it (itself plus j-1 stacked). Greedily accumulate 1, 2, 3, ... until the total added covers the remainder.
Visual walkthrough for n = 15:
- binary search: s=3 gives 3*4*5/6 = 10 <= 15; s=4 gives 4*5*6/6 = 20 > 15, so s=3.
- pyramid ground = 3*4/2 = 6; total = 10; remainder = 5.
- add new row: j=1 adds 1 (run 1), j=2 adds 2 (run 3), j=3 adds 3 (run 6 >= 5).
- new ground cubes = 3. Answer = 6 + 3 = 9.
Check against known cases: n=3 gives s=2, total 3, remainder 0, answer 3; n=10 gives s=3, total 10, remainder 0, answer 6; n=4 gives s=2, total 4, remainder 0, answer 3.
Optimal Approach
A ground cube supports a whole stack, so the cheapest layout is a stair pyramid. Binary-search the largest s whose total volume s(s+1)(s+2)/6 is at most n, and record its ground count s(s+1)/2 plus used cubes. Then handle the remainder r: keep adding the next ground cube of the extended triangle row, where the j-th cube adds j more cube positions, until the accumulated total reaches r.
Walkthrough for n = 4:
- Try s=1: 123/6 = 1 <= 4. Try s=2: 234/6 = 4 <= 4. Try s=3: 3*4*5/6 = 10 > 4. So s=2.
- Used = 4, remainder = 0, ground so far = 2*3/2 = 3.
- Answer = 3.
Time: O(k) where k is the pyramid side, capped near 2000 for n <= 10^9 (effectively constant); space: O(1).
What Trips People Up in Real Interviews
Simulating cube by cube. With n up to a billion any loop touching each cube individually times out. The pyramid formulas compress everything into O(1)-class math.
Swapping the two formulas. The ground layer of a side-s triangle is s(s+1)/2; the full pyramid is s(s+1)(s+2)/6. Flipping them corrupts the binary search threshold and the final ground count.
Forgetting the second phase entirely. Finding the largest full pyramid is only half the problem - leftover cubes still demand new ground boxes. Skipping the greedy remainder step under-reports the answer.
Off-by-one in the binary search. You want the largest s whose pyramid fits (<= n). Use the seek-largest form mid = (lo + hi + 1) / 2 and move hi down when the candidate overflows.
Integer overflow in s(s+1)(s+2). The product reaches the 10^9 range, so compute in a 64-bit type (natural in Python, but C++ and Java need long) before dividing by 6.
Solution Code
def minimumBoxes(n):
lo, hi = 0, 2000
while lo < hi:
mid = (lo + hi + 1) // 2
if mid * (mid + 1) * (mid + 2) // 6 <= n:
lo = mid
else:
hi = mid - 1
s = lo
total = s * (s + 1) * (s + 2) // 6
answer = s * (s + 1) // 2
remaining = n - total
added = 0
row = 0
while added < remaining:
row += 1
answer += 1
added += row
return answerFrequently Asked Questions
What is the Building Boxes problem?
With n unit cubes, build a house where every cube above the ground layer is supported by a cube directly beneath it, minimizing the number of cubes that touch the ground. This greedy-with-binary-search hard problem is a signature Adobe math question with n up to one billion.
How do you solve Building Boxes?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Building Boxes?
Building Boxes is asked at Adobe. It is a hard difficulty problem.
What are common mistakes on Building Boxes?
- Simulating cube by cube. With n up to a billion any loop touching each cube individually times out. The pyramid formulas compress everything into `O(1)`-class math.
- Swapping the two formulas. The ground layer of a side-s triangle is `s(s+1)/2`; the full pyramid is `s(s+1)(s+2)/6`. Flipping them corrupts the binary search threshold and the final ground count.
- Forgetting the second phase entirely. Finding the largest full pyramid is only half the problem - leftover cubes still demand new ground boxes. Skipping the greedy remainder step under-reports the answer.
- Off-by-one in the binary search. You want the largest s whose pyramid fits (`<= n`). Use the seek-largest form `mid = (lo + hi + 1) / 2` and move hi down when the candidate overflows.
- Integer overflow in `s(s+1)(s+2)`. The product reaches the 10^9 range, so compute in a 64-bit type (natural in Python, but C++ and Java need `long`) before dividing by 6.