An orchard manager has exactly n saplings to plant and wants to lay them out in a single rectangular grid with w columns and h rows, using every sapling exactly once (so w * h = n). Company policy requires the grid to look as close to a perfect square as possible, so among all valid (w, h) layouts she must pick the one that minimizes w - h; the number of columns can never be smaller than the number of rows (w >= h). Given n, find the dimensions of this layout.
A single integer n on one line: the total number of saplings.
Two space-separated integers w and h on one line, satisfying w * h = n, w >= h > 0, with w - h as small as possible.
Example 1
Input
4
Expected
2 2
Explanation
4 factors as 1*4 or 2*2. With w>=h, the candidate pairs are (4,1) with difference 3 and (2,2) with difference 0. The smallest difference is 0, so the answer is w=2, h=2.
Example 2
Input
37
Expected
37 1
Explanation
37 is prime, so its only factor pair with w>=h is (37, 1). That pair is forced regardless of how close to square it looks.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →