Building boxes

Math Binary Search Greedy

52.4% acceptance

Feb 25, 2026

314

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. Rules: 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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_boxes(n: i32) -> i32 {
    let n = n as i64;
    // Find largest h such that h*(h+1)*(h+2)/6 <= n (complete triangular pyramid)
    let mut h = 0i64;
    while (h + 1) * (h + 2) * (h + 3) / 6 <= n {
      h += 1;
    }
    let total = h * (h + 1) * (h + 2) / 6;
    let floor = h * (h + 1) / 2;
    let remaining = n - total;
    // Find smallest j with j*(j+1)/2 >= remaining
    let mut j = 0i64;
    while j * (j + 1) / 2 < remaining {
      j += 1;
    }
    (floor + j) as i32
  }
}