Ninja’s Apartment

Easy
0/40
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in companies
InfosysGoldman Sachs

Problem statement

Ninja is planning to build a new apartment but he wants an apartment in the shape of a rectangle whose length is greater than the breadth of the rectangle. Also, the difference between the length and breadth should be minimum for the area of the apartment.

So your task is to print the length and breadth of the rectangle. You are provided with the ‘AREA’ of the region in which the apartment is to be built.

Example:

Suppose given ‘AREA’ is ‘6’. So, possible combinations are [ [ 1, 6 ], [ 2, 3 ], [ 3, 2 ], [ 6, 1 ] ]. We can’t choose [ 1, 6 ], [ 2, 3 ] as in this case breadth is greater than length.
So, we choose [ 3, 2 ] over [ 6, 1 ] as the difference between | 3 - 2 | < | 6 - 1 | so we return | 3, 2 | as the answer.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a ‘T’ number of test cases.
The first line of each test case contains an integer ‘AREA’ denoting the area of the rectangle.

Output Format:

For each test case, print the length and breadth of the given area.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 10^2
2 <= ‘AREA’ <= 10 ^ 6

Where ‘T’ represents the number of test cases and ‘AREA’ represents the given area of the apartment.

Time Limit: 1sec

Sample Input 1:

2
12
8

Sample Output 1:

4 3
4 2

Explanation For Sample Input 1:

In the first test case,

Given ‘AREA’ is ‘12’ so possible combinations are [ [ 1, 12 ], [ 2, 6 ], [ 3, 4 ], [ 4, 3 ], [ 6, 2 ], [ 12, 1 ] ]. We can’t choose [ 1, 12 ], [ 2, 6 ], [ 3, 4 ] as in this case breadth is greater than length.
We choose [ 4, 3 ] over [ 6, 2 ]  and [ 12, 1 ] as the difference between | 4 - 3 | < | 6 - 2 | and | 4 - 3 | < | 12 - 1 |  so we print | 4, 3 | as the answer.

In the second test case,

Given ‘AREA’ is ‘8’ so possible combinations are [ [ 1, 8 ], [ 2, 4 ], [ 4, 2 ], [8, 1 ] ]. We cant choose [ 1, 8 ], [ 2, 4 ] as in this case breadth is greater than length.
We choose [ 4, 2 ] over [ 8, 1 ] as the difference between | 4 - 2 | < | 8 - 1 | so we print | 3, 2 | as the answer.

Sample Input 1:

2
17
16

Sample Output 1:

17 1
4 4

Explanation For Sample Input 2:

In the first test case,

Given ‘AREA’ is ‘17’ so possible combinations are [ [ 1, 17 ], [ 17, 1 ] ]. We can’t choose [ 1, 17 ] as in this case breadth is greater than length.
We choose [ 17, 1]  and so we print | 17, 1 | as the answer.

In the second test case,

Given ‘AREA’ is ‘16’ so possible combinations are [ [ 1, 16 ], [ 2, 8 ], [ 4, 4], [ 8, 2 ], [16, 1 ] ]. We cant choose [ 1, 16 ], [ 2, 8 ] as in this case breadth is greater than length.
We choose [ 4, 4 ] over [ 8, 2 ] and [16,1] as the difference between | 4 - 4 | < | 8 - 2 | so we print | 4, 4 | as the answer.
Hint

Can you compare the difference of each and every possible length and breadth?

Approaches (2)
Brute Approach

Approach: The idea here is to use a brute approach. Starting from ‘1’ up to ‘AREA’, we run a loop and compare the differences of length and breadth and one with the minimum is our answer.

 

Algorithm is as follows:

  1. First, we declare an array/list named ‘ANS’.
  2. Now we run a loop starting ‘i’ from ‘1’ up to ‘AREA’’ and for every iteration we check:
    • If the ‘AREA’ is multiple of ‘i’:
      • If ‘AREA % i == 0’ then ‘i’ becomes our length. Now we find the breadth by dividing the is by ‘i’.
      • Now we check if the breadth is smaller than the length.
        • We compare it with ‘MIN’. If ‘MIN’ is greater than their difference we update our length and breadth and push it into the ‘ANS’.
      • Else we continue the loop.
    • Else we continue the loop.
  3. In the end, we return ‘ANS’.
Time Complexity

O(N), where ‘N’ is the given value of the area.

 

As we are iterating from ‘1’ upto ‘AREA’.

Space Complexity

O(1).

 

As we are using constant space.

Code Solution
(100% EXP penalty)
Ninja’s Apartment
Full screen
Console