Last Updated: 19 Apr, 2021
Kth factor of a number
Moderate
Asked in companies
You are given two positive integers ‘N’ and ‘K’. You have to find the ‘K’-th factor of ‘N’, where the ‘K’-th factor is the ‘K’-th number in a sequence of all the factors of ‘N’ arranged in ascending order.
For example:
If N = 12 and K = 5, then we have to find the 5’th factor of 12 out of the list of all factors of 12 : [1, 2, 3, 4, 6, 12], the 5’th factor in the list is 6. Hence, the output is 6.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then ‘T’ test cases follow:
The first and only line in each test case contains two space-separated positive integers ‘N’ and ‘K’, where 'N' is the positive integer whose factor is to be found, ‘K’ is the ‘K’th number in a sequence of all the factors of ‘N’ arranged in ascending order.
Output Format:
For each test case, return the ‘K’th factor of the given positive integer ‘N’. If the ‘K’th factor does not exist, print -1.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 50
1 <= N <= 10^5
1 <= K <= N
Time limit: 1 sec
Approaches
The idea is to simply check each number from 1 to ‘X’ whether it is a factor of ‘X’ or not, where ‘X’ is the positive integer whose ‘Kth’ factor is to be found.
The steps are as follows:
- Declare a variable ‘COUNT’ in which we store the ‘K’th factor and initialize it with 0.
- Run a loop for ‘i’ = 1 to ‘N’:
- If the current number is a factor of ‘N’:
- Increment ‘COUNT’ by 1.
- If at any iteration, the value of ‘COUNT’ becomes equal to ‘K’, that means we have reached the ‘Kth’ factor:
- Return ‘COUNT’.
- If the current number is a factor of ‘N’:
- If the value of ‘COUNT’ remains less than ‘K’, it means, ‘Kth’ factor doesn’t exist.
- Return -1.
This approach works because the upper limit till which we need to iterate to find all the factors of ‘N’ is ‘square root of (N)’.
Why is “square root of (N)” is the upper limit?.
- {square root of (N)} * {square root of (N)} = N.
- So if the two factors of ‘N’ are the same, they're both equal to the ‘square root of (N)’. If we make one factor bigger, we will have to make the other factor smaller such that their product is equal to ‘N’.
- From this, it can be concluded that if one of these factors is greater, the other factor is bound to be smaller than the ‘square root of (N)’.
- Hence, we only need to iterate till both the factors become equal (till ‘square root of (N)’) to find all the factors of ‘N’ because after ‘square root of (N)’, the pairs of [‘i’ , ‘N’/’i’] will be repeated as [‘N’/’i’ , ‘i’], where ‘i’ a factor of ‘N’ less than ‘square root of (N)’.
We will use this idea to find the ‘Kth’ factor of ‘N’.
The steps are as follows:
- Declare a variable ‘COUNT’ and initialize it with 0, which will count the number of factors encountered till now.
- Create an iterator variable ‘i’ to iterate through the loop.
- Run a loop from 1 to “square root of (N)” (here, iterator = ‘i’):
- If the current number ‘i’ is a factor of ‘N’:
- Increment ‘COUNT’ by 1
- If the value of ‘COUNT’ becomes equal to ‘K’:
- Return ‘i’ as the answer.
- If the current number ‘i’ is a factor of ‘N’:
- If ‘count’ is still less than ‘K’, the answer may be a factor greater than “square root of (K)”.
- To find it, run a loop from ‘i-1’ to 1 (say, iterator = ‘j’), where ‘i’ is the iterator from the previous loop.
- If the current number ‘j’ is a factor of ‘N’:
- Increment ‘COUNT’ by 1
- If the value of ‘COUNT’ becomes equal to ‘K’:
- Return ‘N’/’j’ as the answer.
- If the current number ‘j’ is a factor of ‘N’:
- If ‘COUNT’ is still less than ‘K’, then the ‘Kth’ factor doesn’t exist:
- Return -1.