Problem Statement: Kth Factor of a Number

Description:

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. If there is no k-th factor, return -1.

Input Format

Takes two integers n and k as input, where n is the number and k is the k-th factor of n.

Constraints

1 <= N <= 10^5
1 <= K <= N

Output Format

Returns a single integer as answer.

Sample Input:

10 3
11 4

Sample Output:

5
-1

Explanation:

• In the first example, n=10 and k=3, now the factors of 10 are [1,2,5,10] and 3rd factor is 5, so the answer is 5.
• In the second example, n=11 and k=4, now the factors of 11 are [1,11] and there is no 4th factor, so we return -1 as the answer.

Now try it yourself
.
.
.
.
.
.
.
.
.
Hint 1: You can iterate through all the factors of n to reach the k-th factor.
.
.
.
.
.
.
.

Solution:

//using cpp

#include<bits/stdc++.h>
using namespace std;
int kth_factor(int n, int k){
    int count=0;
    for(int i=1;i<=n;i++){
        if(n%i==0){
           count++;
           if(count==k)
           return i;           
           }
         }
   return -1;
}
int main(){
    int n,k;
    cin>>n>>k;
    cout<<"The kth factor of n is: "<<kth_factor(n,k);
    return 0;
}

Time complexity: O(n)
Space Complexity: O(1)

Code Explanation:

• The count variable counts the number of factors of n.
• If count = k, then i is the k-th factor of n.
• If the loop ends, and there is no value returned, it means there is no k-th factor of n, so we return -1.

Follow Up Question: Can you reduce the time complexity of this function
.
.
.
.
.
.
.
Hint 2: Do you really need to iterate to n for all the factors
.
.
.
.
.
.
.
.
.
.

Solution:

//using cpp

#include<bits/stdc++.h>
using namespace std;
int kth_factor(int n, int k){
    int i,ct=0;
    for(i=1;i*i<=n;i++){
        if(n%i==0){
            ct++;
            if(ct==k)
            return i;
        }
        if(i==(float)n/i)
        ct--;
    }
    for(int j=i-1;j>=1;j--){
        if(n%j==0){
            ct++;
            if(ct==k)
            return (n/j);
        }
    }
    return -1;
}
int main(){
    int n,k;
    cin>>n>>k;
    cout<<"The kth factor of n is : "<<kth_factor(n,k);
    return 0;
}

Time Complexity: O(sqrt n)
Space Complexity: O(1)

Code Explanation:

• We take ct as a variable that counts the number of factors of n.
• We run loop from 1 to square root of n.
• The basic logic we used is that If i is the factor of n then n/i is also the factor of nand If i is less than square root of n than n/i will be greater than square root of n.
• If we do no get the value of k-th factor from the first loop, it means that either k-th factor do not exist of is greater than square root of n.
• We check if n is a perfect square or not by checking if i equals to float value of n/i or not.
  • Why do we need to check for perfect square?
  • If n is the perfect square, then program will count it's square root as two seperate factors, and then our answer will be wrong.
  • Now why do we need to compare i to float value of n/i?
  • Let's take a example of n=10, now the square root of 10 will be given as 3(as integer value is considered) and 10/3 is also equals to 3, but we all know that 10 is not a perfect square, so that's why we take float value of n/i.
• So we take the second loop that starts from i-1 and goes upto 1.Now if j divides n then we increase the count and check if that is k-th factor or not and if true, then this time we return n/j as the answer.
• If we do not get answer from either loops,then it means the k-th factor does not exist, so we return -1 as the answer.

Additional Information:

• This question had been asked in interview of companies like Amazon and Deloitte.

Hope you understand..

Happy coding!!!