{"id":8034,"date":"2021-01-23T22:48:28","date_gmt":"2021-01-24T06:48:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8034"},"modified":"2021-01-23T22:57:48","modified_gmt":"2021-01-24T06:57:48","slug":"leetcode-1739-building-boxes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1739-building-boxes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1739. Building Boxes"},"content":{"rendered":"\n<p>You have a cubic storeroom where the width, length, and height of the room are all equal to&nbsp;<code>n<\/code>&nbsp;units. You are asked to place&nbsp;<code>n<\/code>&nbsp;boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>You can place the boxes anywhere on the floor.<\/li><li>If box&nbsp;<code>x<\/code>&nbsp;is placed on top of the box&nbsp;<code>y<\/code>, then each side of the four vertical sides of the box&nbsp;<code>y<\/code>&nbsp;<strong>must<\/strong>&nbsp;either be adjacent to another box or to a wall.<\/li><\/ul>\n\n\n\n<p>Given an integer&nbsp;<code>n<\/code>, return<em>&nbsp;the&nbsp;<strong>minimum<\/strong>&nbsp;possible number of boxes touching the floor.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/01\/04\/3-boxes.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> The figure above is for the placement of the three boxes.\nThese boxes are placed in the corner of the room, where the corner is on the left side.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/01\/04\/4-boxes.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 4\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> The figure above is for the placement of the four boxes.\nThese boxes are placed in the corner of the room, where the corner is on the left side.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/01\/04\/10-boxes.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 10\n<strong>Output:<\/strong> 6\n<strong>Explanation:<\/strong> The figure above is for the placement of the ten boxes.\nThese boxes are placed in the corner of the room, where the corner is on the back side.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Geometry<\/strong><\/h2>\n\n\n\n<p>Step 1: Build a largest pyramid that has less then n cubes, whose base area is d*(d+1) \/ 2<br>Step 2: Build a largest triangle with cubes left, whose base area is l, l*(l + 1) \/ 2 &gt;= left<\/p>\n\n\n\n<p>Time complexity: O(n^(1\/3))<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumBoxes(int n) {\n    int d = 0;\n    int l = 0;\n    while (n - (d + 1) * (d + 2) \/ 2 > 0) {\n      n -= (d + 1) * (d + 2) \/ 2;\n      ++d;\n    }\n    while (n > 0) n -= ++l;\n    return d * (d + 1) \/ 2 + l;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You have a cubic storeroom where the width, length, and height of the room are all equal to&nbsp;n&nbsp;units. You are asked to place&nbsp;n&nbsp;boxes in this&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[284,31,694,293],"class_list":["post-8034","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-math","tag-pyramid","tag-triangle","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8034","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8034"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8034\/revisions"}],"predecessor-version":[{"id":8039,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8034\/revisions\/8039"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8034"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8034"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8034"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}