LeetCode 1492: The kth Factor of n
Problem Description
Explanation
To solve this problem efficiently, we can iterate from 1 to sqrt(n) and for each divisor i, we can check if n % i == 0. If it is true, then both i and n/i are factors of n. We can add them to a list and keep track of the count of factors found. Once we reach k factors, we return the kth factor. If k exceeds the count of factors found, we return -1.
- Time complexity: O(sqrt(n))
- Space complexity: O(k)
Solutions
class Solution {
public int kthFactor(int n, int k) {
List<Integer> factors = new ArrayList<>();
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
factors.add(i);
if (i != n / i) {
factors.add(n / i);
}
}
}
if (k > factors.size()) {
return -1;
}
return factors.get(k - 1);
}
}Loading editor...