Last Updated: 14 Apr, 2021

Closest Divisors

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now