{"id":2883,"date":"2018-06-02T13:00:10","date_gmt":"2018-06-02T20:00:10","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2883"},"modified":"2018-06-02T13:00:32","modified_gmt":"2018-06-02T20:00:32","slug":"leetcode-492-construct-the-rectangle","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-492-construct-the-rectangle\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 492. Construct the Rectangle"},"content":{"rendered":"

Problem<\/h1>\n

For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page\u2019s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:<\/p>\n

1. The area of the rectangular web page you designed must equal to the given target area.\r\n\r\n2. The width W should not be larger than the length L, which means L >= W.\r\n\r\n3. The difference between length L and width W should be as small as possible.\r\n<\/pre>\n
You need to output the length L and the width W of the web page you designed in sequence.<\/p>\n
Example:<\/b><\/p>\n
Input:<\/b> 4\r\nOutput:<\/b> [2, 2]\r\nExplanation:<\/b> The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1]. \r\nBut according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.\r\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. The given area won’t exceed 10,000,000 and is a positive integer<\/li>\n
  2. The web page’s width and length you designed must be positive integers.<\/li>\n<\/ol>\n
    Solution<\/strong><\/h1>\n
    Time complexity: O(sqrt(n))<\/p>\n
    Space complexity: O(1)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 3 ms (<98.48%)\r\nclass Solution {\r\npublic:\r\n  vector<int> constructRectangle(int area) {    \r\n    for (int i = sqrt(area); i >= 1; --i)\r\n      if (area % i == 0) return {area \/ i, i};    \r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page\u2019s…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,61],"class_list":["post-2883","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-sqrt","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2883","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=2883"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2883\/revisions"}],"predecessor-version":[{"id":2885,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2883\/revisions\/2885"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2883"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2883"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2883"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}