The kth Factor of n
MedPrompt
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?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves a straightforward linear scan through all numbers from 1 to n. For each number, we check if it's a factor of n. We use a counter to keep track of how many factors we've found. When the counter reaches k, we've found our target and can return the current number.
Algorithm
- Initialize a counter
countto 0. - Iterate with a loop variable
ifrom1ton. - Inside the loop, check if
iis a factor ofnusing the modulo operator (n % i == 0). - If
iis a factor, incrementcount. - If
countbecomes equal tok, it meansiis the k-th factor. Returniimmediately. - If the loop completes without the
countreachingk, it implies thatnhas fewer thankfactors. In this case, return-1.
Walkthrough
The brute-force algorithm is the most intuitive way to solve this problem. We simply iterate through all possible candidates for factors, which are the integers from 1 up to n.
We maintain a counter, initialized to zero. As we iterate, if we find a number i that divides n evenly (n % i == 0), we've found a factor. Since we are iterating in ascending order, the first factor we find is the 1st factor, the second is the 2nd, and so on. We increment our counter for each factor found. As soon as our counter equals k, we have located the k-th factor and can return it. If we iterate through all numbers up to n and the counter never reaches k, it means n has fewer than k factors, and we should return -1 as per the problem description.
class Solution { public int kthFactor(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; }}Complexity
Time
O(n). In the worst-case scenario, we might have to iterate through all numbers from 1 to `n` to find the k-th factor or to determine that it doesn't exist.
Space
O(1). We only use a few variables to store the counter and the loop index, regardless of the size of `n`.
Trade-offs
Pros
Very simple to understand and implement.
Requires minimal memory (constant space complexity).
Cons
The time complexity is linear with respect to
n, which can be slow ifnis very large. For the given constraints (n <= 1000), it's acceptable, but it doesn't scale well.
Solutions
Solution
class Solution {public int kthFactor(int n, int k) { for (int i = 1; i <= n; ++i) { if (n % i == 0 && (--k == 0)) { return i; } } return -1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.