The Algorithm to Construct the Rectangle Given Its Area
- 时间:2020-09-30 16:23:25
- 分类:网络文摘
- 阅读:68 次
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’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:
- The area of the rectangular web page you designed must equal to the given target area.
- The width W should not be larger than the length L, which means L >= W.
- The difference between length L and width W should be as small as possible.
You need to output the length L and the width W of the web page you designed in sequence.
Example:
Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1].But 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.
Note:
The given area won’t exceed 10,000,000 and is a positive integer
The web page’s width and length you designed must be positive integers.
Math Algorithm
To construct the optimal rectangle that its width and height difference is minimal, we can start from the square root of the area, and search in either directions incrementing or decrementing by one until width and height are both integers.
The edge case is when input area is smaller or equal to zero. The following bruteforce algorithm searches upwards:
1 2 3 4 5 6 7 8 9 10 | class Solution { public int[] constructRectangle(int area) { if (area == 0) return new int[] {0, 0}; int x = (int)Math.ceil(Math.sqrt(area)); while (area % x != 0) { x ++; } return new int[] { x, area / x }; } } |
class Solution { public int[] constructRectangle(int area) { if (area == 0) return new int[] {0, 0}; int x = (int)Math.ceil(Math.sqrt(area)); while (area % x != 0) { x ++; } return new int[] { x, area / x }; } }
And the following Java implementation is also accepted which searches downwards (in the other direction):
1 2 3 4 5 6 7 8 9 10 | class Solution { public int[] constructRectangle(int area) { if (area == 0) return new int[] {0, 0}; int x = (int)(Math.sqrt(area)); while (area % x != 0) { x --; } return new int[] { area / x, x }; } } |
class Solution { public int[] constructRectangle(int area) { if (area == 0) return new int[] {0, 0}; int x = (int)(Math.sqrt(area)); while (area % x != 0) { x --; } return new int[] { area / x, x }; } }
When input area is invalid (negative numbers), you could let the code throw exception (divide by zero) or throw exception by yourself, or simply return {-1, -1}. The following is also accepted, although a bit verbose.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public int[] constructRectangle(int area) { if (area == 0) return new int[] {0, 0}; int x = (int)Math.sqrt(area); while (x <= area) { if (area % x == 0) { int min = Math.min(x, area / x); int max = Math.max(x, area / x); return new int[] { max, min }; } x ++; } return new int[] { -1, -1 }; // should not reach here. } } |
class Solution { public int[] constructRectangle(int area) { if (area == 0) return new int[] {0, 0}; int x = (int)Math.sqrt(area); while (x <= area) { if (area % x == 0) { int min = Math.min(x, area / x); int max = Math.max(x, area / x); return new int[] { max, min }; } x ++; } return new int[] { -1, -1 }; // should not reach here. } }
The complexity is O(Sqrt(N)) time, and O(1) constant space.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:嚼食槟榔对身体健康的危害非常大 槟榔被认定为一级致癌物可引发口腔癌 食品安全监管工作的有效性令人疑惑 厂家称没法根本解决五芳斋粽子发霉 饮食保健:盘点枸杞的十大养生功效 食物为何会致癌及常见致癌物来源 肯德基麦当劳可食用冰块菌落超标 南瓜的保健作用:降血糖血脂、防癌 大暑养生:暑天应多吃清淡易消化食物 市场热俏的功能性饮料到底是什么?
- 评论列表
-
- 添加评论