You’re given a number N and a number K. Our task is to find the kth smallest divisor of N.
Examples:
Input : N = 12, K = 5 Output : 6 The divisors of 12 after sorting are 1, 2, 3, 4, 6 and 12. Where the value of 5th divisor is equal to 6. Input : N = 16, K 2 Output : 2
Simple Approach: A simple approach is to run a loop from 1 to √N and find all factors of N and push them into a vector. Finally, sort the vector and print the K-th value from the vector.
Note: Elements in the vector will not be sorted initially as we are pushing both factors (i) and (n/i). That is why it is needed to sort the vector before printing the K-th factor.
Below is the implementation of the above approach :
C++
// C++ program to find K-th smallest factor#include <bits/stdc++.h>using namespace std;// function to find the k'th divisorvoid findkth(int n, int k){ // initialize a vector v vector<long long> v; // store all the divisors // so the loop will needs to run till sqrt ( n ) for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { v.push_back(i); if (i != sqrt(n)) v.push_back(n / i); } } // sort the vector in an increasing order sort(v.begin(), v.end()); // if k is greater than the size of vector // then no divisor can be possible if (k > v.size()) cout << "Doesn't Exist"; // else print the ( k - 1 )th value of vector else cout << v[k - 1];}// Driver codeint main(){ int n = 15, k = 2; findkth(n, k); return 0;} |
Java
// Java program to find K-th smallest factorimport java.util.*;class GFG{// function to find the k'th divisorstatic void findkth(int n, int k){ // initialize a vector v Vector<Integer> v = new Vector<Integer>(); // store all the divisors // so the loop will needs to run till sqrt ( n ) for (int i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { v.add(i); if (i != Math.sqrt(n)) v.add(n / i); } } // sort the vector in an increasing order Collections.sort(v); // if k is greater than the size of vector // then no divisor can be possible if (k > v.size()) System.out.print("Doesn't Exist"); // else print the ( k - 1 )th value of vector else System.out.print(v.get(k - 1));}// Driver codepublic static void main(String[] args){ int n = 15, k = 2; findkth(n, k);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find K-th smallest factorfrom math import sqrt# function to find the k'th divisordef findkth(n, k): # initialize a vector v v = [] # store all the divisors so the loop # will needs to run till sqrt ( n ) p = int(sqrt(n)) + 1 for i in range(1, p, 1): if (n % i == 0): v.append(i) if (i != sqrt(n)): v.append(n / i); # sort the vector in an increasing order v.sort(reverse = False) # if k is greater than the size of vector # then no divisor can be possible if (k > len(v)): print("Doesn't Exist") # else print the (k - 1)th # value of vector else: print(v[k - 1])# Driver codeif __name__ == '__main__': n = 15 k = 2 findkth(n, k)# This code is contributed by# Surendra_Gangwar |
C#
// C# program to find K-th smallest factorusing System;using System.Collections.Generic;class GFG{ // function to find the k'th divisorstatic void findkth(int n, int k){ // initialize a vector v List<int> v = new List<int>(); // store all the divisors // so the loop will needs to run till sqrt ( n ) for (int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { v.Add(i); if (i != Math.Sqrt(n)) v.Add(n / i); } } // sort the vector in an increasing order v.Sort(); // if k is greater than the size of vector // then no divisor can be possible if (k > v.Count) Console.Write("Doesn't Exist"); // else print the ( k - 1 )th value of vector else Console.Write(v[k - 1]);} // Driver codepublic static void Main(String[] args){ int n = 15, k = 2; findkth(n, k);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>function findkth( n, k){ // initialize a vector v var v=[]; // store all the divisors // so the loop will needs to run till sqrt ( n ) for (var i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { v.push(i); if (i != Math.sqrt(n)) v.push(n / i); } } // sort the vector in an increasing order v.sort(function fun(a,b){ return a-b }); // if k is greater than the size of vector // then no divisor can be possible if (k > v.length) document.write("Doesn't Exist"); // else print the ( k - 1 )th value of vector else document.write( v[k - 1]);}var n = 15, k = 2; findkth(n, k);</script> |
Output
3
Time Complexity: √N log( √N )
Efficient Approach: An efficient approach will be to store the factors in two separate vectors. That is, factors i will be stored in a separate vector and N/i will be stored in a separate vector for all i from 1 to √N.
Now, if observed carefully, it can be seen that the first vector is already sorted in increasing order and the second vector is sorted in decreasing order. So, reverse the second vector and print the K-th element from either of the vectors in which it is lying.
Below is the implementation of the above approach:
C++
// C++ program to find the K-th smallest factor#include <bits/stdc++.h>using namespace std;// Function to find the k'th divisorvoid findkth ( int n, int k){ // initialize vectors v1 and v2 vector <int> v1; vector <int> v2; // store all the divisors in the two vectors // accordingly for( int i = 1 ; i <= sqrt( n ); i++ ) { if ( n % i == 0 ) { v1.push_back ( i ); if ( i != sqrt ( n ) ) v2.push_back ( n / i ); } } // reverse the vector v2 to sort it // in increasing order reverse(v2.begin(), v2.end()); // if k is greater than the size of vectors // then no divisor can be possible if ( k > (v1.size() + v2.size())) cout << "Doesn't Exist" ; // else print the ( k - 1 )th value of vector else { // If K is lying in first vector if(k <= v1.size()) cout<<v1[k-1]; // If K is lying in second vector else cout<<v2[k-v1.size()-1]; }}// Driver codeint main(){ int n = 15, k = 2; findkth ( n, k) ; return 0;} |
Java
// Java program to find the K-th smallest factorimport java.util.*;class GFG{// Function to find the k'th divisorstatic void findkth ( int n, int k){ // initialize vectors v1 and v2 Vector<Integer> v1 = new Vector<Integer>(); Vector <Integer> v2 = new Vector<Integer>(); // store all the divisors in the two vectors // accordingly for( int i = 1 ; i <= Math.sqrt( n ); i++ ) { if ( n % i == 0 ) { v1.add ( i ); if ( i != Math.sqrt ( n ) ) v2.add ( n / i ); } } // reverse the vector v2 to sort it // in increasing order Collections.reverse(v2); // if k is greater than the size of vectors // then no divisor can be possible if ( k > (v1.size() + v2.size())) System.out.print("Doesn't Exist"); // else print the ( k - 1 )th value of vector else { // If K is lying in first vector if(k <= v1.size()) System.out.print(v1.get(k - 1)); // If K is lying in second vector else System.out.print(v2.get(k-v1.size() - 1)); }}// Driver codepublic static void main(String[] args){ int n = 15, k = 2; findkth ( n, k) ;}} // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find the K-th # smallest factorimport math as mt# Function to find the k'th divisordef findkth (n, k): # initialize vectors v1 and v2 v1 = list() v2 = list() # store all the divisors in the # two vectors accordingly for i in range(1, mt.ceil(n**(.5))): if (n % i == 0): v1.append(i) if (i != mt.ceil(mt.sqrt(n))): v2.append(n // i) # reverse the vector v2 to sort it # in increasing order v2[::-1] # if k is greater than the size of vectors # then no divisor can be possible if ( k > (len(v1) + len(v2))): print("Doesn't Exist", end = "") # else print the ( k - 1 )th value of vector else: # If K is lying in first vector if(k <= len(v1)): print(v1[k - 1]) # If K is lying in second vector else: print(v2[k - len(v1) - 1]) # Driver coden = 15k = 2findkth (n, k) # This code is contributed by Mohit kumar |
C#
// C# program to find // the K-th smallest factorusing System;using System.Collections.Generic;class GFG{// Function to find the k'th divisorstatic void findkth (int n, int k){ // initialize vectors v1 and v2 List<int> v1 = new List<int>(); List <int> v2 = new List<int>(); // store all the divisors in the // two vectors accordingly for(int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { v1.Add (i); if (i != Math.Sqrt (n)) v2.Add (n / i); } } // reverse the vector v2 to sort it // in increasing order v2.Reverse(); // if k is greater than the // size of vectors then no // divisor can be possible if (k > (v1.Count + v2.Count)) Console.Write("Doesn't Exist"); // else print the (k - 1)th // value of vector else { // If K is lying in first vector if(k <= v1.Count) Console.Write(v1[k - 1]); // If K is lying in second vector else Console.Write(v2[k - v1.Count - 1]); }}// Driver codepublic static void Main(String[] args){ int n = 15, k = 2; findkth (n, k);}} // This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program to find the K-th smallest factor // Function to find the k'th divisorfunction findkth ( n,k){ // initialize vectors v1 and v2 let v1 = []; let v2 = []; // store all the divisors in the two vectors // accordingly for( let i = 1 ; i <= Math.sqrt( n ); i++ ) { if ( n % i == 0 ) { v1.push ( i ); if ( i != Math.sqrt ( n ) ) v2.push ( n / i ); } } // reverse the vector v2 to sort it // in increasing order v2.reverse(); // if k is greater than the size of vectors // then no divisor can be possible if ( k > (v1.length + v2.length)) document.write("Doesn't Exist"); // else print the ( k - 1 )th value of vector else { // If K is lying in first vector if(k <= v1.length) document.write(v1[k - 1]); // If K is lying in second vector else document.write(v2[k-v1.length - 1]); }}// Driver codelet n = 15, k = 2;findkth ( n, k) ;// This code is contributed by unknown2108</script> |
Output:
3
Time Complexity: √N
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
