Closest Divisors

Moderate

0/80

Average time to solve is 25m

Contributed by

5 upvotes

Asked in company

Problem statement

You are given an integer ‘NUM’. Your task is to find out two numbers ‘FIRST’ and ‘SECOND’ such that their product is equal to either ‘NUM’ + 1 or ‘NUM’ + 2 and their absolute difference is the minimum between all such pairs.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.

The first line of each test case contains a single positive integer, ‘NUM’.

Output Format:

For each test case, print 2 integers ‘FIRST’ and ‘SECOND’ as described in the problem statement and 'FIRST <= 'SECOND'.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘NUM’ <= 10^8

Time Limit: 1 sec

Sample Input 1:

1
10

Sample Output 1:

3 4

Explanation For Sample Input 1:

‘NUM’ + 1 is equal to 11 for which the answer would be 1 and 11, for ‘NUM’ + 2, which is 12 the answer will be 3 and 4. Hence the better answer is 3 and 4.

Sample Input 2:

1
5

Sample Output 2:

2 3

Hint 1

Find all the factors for ‘NUM’ + 1 and choose the best pair amongst them. Repeat the process for ‘NUM’ + 2.

Approaches (1)

Approach 1

Math concepts

Its easy to see that FIRST and SECOND will be factors of ‘NUM+1’ or ‘NUM+2’.
If we can somehow find a factor FIRST of a number N then SECOND will be equal to N/FIRST.
Looking into the constraints of NUM a simple approach will be to find all the factors of NUM + 1 and NUM + 2 till that number sqrt and choose the best answer from amongst them.
To find the factors of a number N simply run a loop till sqrt(N) of that number and check if the current number is divisible by it or not. If yes, then the other factor will be N/i.

Time Complexity

O(sqrt(N)), where N is the number whose factors we are searching, here it is equal to NUM + 1 and NUM + 2.

Factors of a number can be calculated in sqrt(N) time.

Space Complexity

O(1)

We aren’t really storing anything apart from 2 variables FIRST and SECOND.

(100% EXP penalty)

Closest Divisors

Console