In this guide, you will get 1492. The kth Factor of n LeetCode Solution with the best time and space complexity. The solution to The kth Factor of n problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i == 0.
Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.
Example 1:
Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Example 2:
Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.
Example 3:
Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.
Constraints:
1 <= k <= n <= 1000
Follow up:
Could you solve this problem in less than O(n) complexity?
Complexity Analysis
Time Complexity: O(\sqrt{n})
Space Complexity: O(1)
1492. The kth Factor of n LeetCode Solution in C++
class Solution {
public:
int kthFactor(int n, int k) {
// If i is a divisor of n, then n / i is also a divisor of n. So, we can
// find all the divisors of n by processing the numbers <= sqrt(n).
int factor = 1;
int i = 0; // the i-th factor
for (; factor * factor < n; ++factor)
if (n % factor == 0 && ++i == k)
return factor;
for (factor = n / factor; factor >= 1; --factor)
if (n % factor == 0 && ++i == k)
return n / factor;
return -1;
}
}; /* code provided by PROGIEZ */
1492. The kth Factor of n LeetCode Solution in Java
class Solution {
public int kthFactor(int n, int k) {
// If i is a divisor of n, then n / i is also a divisor of n. So, we can
// find all the divisors of n by processing the numbers <= sqrt(n).
int factor = 1;
int i = 0; // the i-th factor
for (; factor * factor < n; ++factor)
if (n % factor == 0 && ++i == k)
return factor;
for (factor = n / factor; factor >= 1; --factor)
if (n % factor == 0 && ++i == k)
return n / factor;
return -1;
}
} // code provided by PROGIEZ
1492. The kth Factor of n LeetCode Solution in Python
class Solution:
def kthFactor(self, n: int, k: int) -> int:
# If i is a divisor of n, then n // i is also a divisor of n. So, we can
# find all the divisors of n by processing the numbers <= sqrt(n).
factor = 1
i = 0 # the i-th factor
while factor < math.isqrt(n):
if n % factor == 0:
i += 1
if i == k:
return factor
factor += 1
factor = n // factor
while factor >= 1:
if n % factor == 0:
i += 1
if i == k:
return n // factor
factor -= 1
return -1 # code by PROGIEZ
