Building Boxes - Practice Coding Problems

Building Boxes - Problem

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.

Input & Output

Example 1 — Small Pyramid

$ Input: n = 3

› Output: 3

💡 Note: With 3 boxes, we need all 3 on the floor since we cannot stack them optimally. Any stacking would require perfect adjacent support which isn't possible with just 3 boxes.

Example 2 — Perfect Pyramid

$ Input: n = 10

› Output: 6

💡 Note: We can build a pyramid with base layer of 6 boxes (arranged in triangular pattern 1+2+3), then add 3 boxes on second level (1+2), then 1 box on top. Total: 6+3+1 = 10 boxes.

Example 3 — Single Box

$ Input: n = 1

› Output: 1

💡 Note: With only 1 box, it must be placed on the floor. Minimum floor boxes = 1.

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

n=10 boxes to place

Stack Optimally

Build pyramid: 6 base + 3 middle + 1 top

Output

6 boxes touching floor

Key Takeaway

🎯 Key Insight: Stack boxes in pyramid formation to maximize height while minimizing base area

Asked in

G Google 15 a Amazon 12

The key insight is to build boxes in pyramid formation to minimize floor usage. The optimal approach uses mathematical formulas for tetrahedral numbers to calculate the minimum base size directly. Time: O(∛n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(∛n)	O(1)	Use pyramid volume formula to calculate optimal base size directly
Binary Search on Answer	O(log n)	O(1)	Binary search on the number of floor boxes to find minimum valid answer
Brute Force Simulation	O(n!)	O(n)	Try all possible box arrangements and find minimum floor boxes

Mathematical Formula — Algorithm Steps

Calculate tetrahedral numbers for different pyramid heights
Find the pyramid that uses exactly n boxes
Return the base area of that pyramid

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Height

Calculate maximum pyramid height h

Calculate Base

Use formula h(h+1)/2 for triangular base

Add Remainder

Place remaining boxes optimally

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int solution(int n) {
    if (n == 1) return 1;
    
    int h = 1;
    while (h * (h + 1) * (h + 2) / 6 <= n) {
        h++;
    }
    h--;
    
    int pyramidBoxes = h * (h + 1) * (h + 2) / 6;
    int remaining = n - pyramidBoxes;
    
    if (remaining == 0) {
        return h * (h + 1) / 2;
    }
    
    int baseBoxes = h * (h + 1) / 2;
    
    int k = 1;
    while (k * (k + 1) / 2 < remaining) {
        k++;
    }
    
    return baseBoxes + k;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(∛n)

Iterate through pyramid heights up to cube root of n

✓ Linear Growth

Space Complexity

O(1)

Only use constant extra variables

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler