Watch 10 video solutions for The kth Factor of n, a medium level problem involving Math, Number Theory. This walkthrough by Naresh Gupta has 5,782 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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?
Problem Overview: Given two integers n and k, return the kth smallest factor of n. A factor is any number that divides n exactly. If n has fewer than k factors, return -1.
Approach 1: Simple Factor Collection (O(n) time, O(n) space)
The most direct solution iterates from 1 to n and checks whether each number divides n. Every time i satisfies n % i == 0, store it in a list of factors. Since iteration happens in ascending order, the list is naturally sorted. After the loop, return the element at index k - 1 if it exists. This approach uses basic iteration and arithmetic checks from math. Time complexity is O(n) because every integer up to n is checked, and space complexity is O(n) in the worst case if many factors are stored.
This method is straightforward and easy to implement. It works well when n is small or when clarity is more important than performance. The drawback is unnecessary work, since most numbers greater than sqrt(n) cannot introduce new factor pairs.
Approach 2: Optimized Factor Collection Using Divisors (O(sqrt(n)) time, O(sqrt(n)) space)
A more efficient method uses the divisor pair property: if i divides n, then n / i is also a factor. Instead of scanning the entire range up to n, iterate only from 1 to sqrt(n). For each valid divisor i, add i to one list and track the paired divisor n / i separately. This relies on core ideas from number theory.
After finishing the loop, you have two ordered groups: small factors and large paired factors. Combine them carefully so the final sequence remains sorted. Then check whether the kth element exists. Because the loop only runs up to sqrt(n), the time complexity becomes O(sqrt(n)), and the space complexity is O(sqrt(n)).
This approach significantly reduces unnecessary checks, especially when n is large. The key insight is recognizing factor symmetry around sqrt(n). It demonstrates practical understanding of divisor enumeration and efficient iteration.
Recommended for interviews: Start by explaining the linear scan approach to show you understand the definition of factors. Then move to the divisor-pair optimization using the sqrt(n) boundary. Interviewers typically expect the O(sqrt(n)) solution because it applies classic divisor enumeration from math and avoids unnecessary iteration.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Factor Collection | O(n) | O(n) | When n is small or when implementing the most straightforward logic |
| Optimized Divisor Enumeration (sqrt method) | O(sqrt(n)) | O(sqrt(n)) | Preferred for large n and typical interview scenarios |