LeetCode 1492 - The kth Factor of n
The problem asks us to find the kth factor of a positive integer n, where the factors are ordered in ascending order. A
Difficulty: 🟡 Medium
Topics: Math, Number Theory
Solution
Problem Understanding
The problem asks us to find the kth factor of a positive integer n, where the factors are ordered in ascending order.
A factor of n is any integer i such that:
$n \bmod i = 0$
For example, if n = 12, the factors are:
[1, 2, 3, 4, 6, 12]
If k = 3, the answer is 3, because 3 is the third element in the sorted factor list.
The important detail is that factors must be considered in ascending order. We are not simply counting divisors, we must identify the exact divisor at position k.
The constraints are:
1 <= k <= n <= 1000
These constraints are relatively small, which means even a straightforward linear scan from 1 to n would work within time limits. However, the follow up explicitly asks whether we can do better than O(n) complexity, which suggests that the intended optimal solution uses mathematical observations about factors.
A few edge cases are important to recognize immediately.
If n is prime, it only has two factors, 1 and n. Any k > 2 must return -1.
If n = 1, the only factor is 1, so k = 1 returns 1, and any larger k returns -1.
Perfect squares are another important case because their square root appears only once as a factor pair. For example:
$16 = 4 \times 4$
We must avoid double counting the square root factor.
Approaches
Brute Force Approach
The simplest solution is to iterate through every integer from 1 to n.
For each number i, we check whether it divides n evenly. If it does, we decrement k. Once k becomes zero, we have found the kth factor and can immediately return it.
This approach is correct because checking every integer guarantees that we encounter all factors in ascending order.
For example, with n = 12:
1 -> factor
2 -> factor
3 -> factor
4 -> factor
...
The moment we encounter the third factor, we return 3.
Although this solution is simple and easy to implement, it requires scanning all numbers up to n in the worst case. That gives a time complexity of O(n).
Optimal Approach
The key mathematical observation is that factors come in pairs.
If i divides n, then:
$i \times \frac{n}{i} = n$
For example, the factor pairs of 12 are:
(1, 12)
(2, 6)
(3, 4)
Notice that once we pass the square root of n, we begin repeating the same pairs in reverse order.
That means we only need to iterate up to:
$\sqrt{n}$
During this iteration:
- Small factors appear in ascending order naturally.
- Their paired large factors appear in descending order.
We can store the larger paired factors temporarily, then process them in reverse later to recover ascending order overall.
This reduces the time complexity from O(n) to O(sqrt(n)).
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Checks every number from 1 to n |
| Optimal | O(sqrt(n)) | O(sqrt(n)) | Uses factor pairs and square root observation |
Algorithm Walkthrough
Optimal Algorithm
- Initialize an empty list called
larger_factors.
This list will store the larger factor from each factor pair. We postpone processing them because they naturally appear in descending order.
2. Iterate from 1 to sqrt(n) inclusive.
We only need to search up to the square root because every factor larger than the square root has a corresponding smaller paired factor.
3. For each number i, check whether it divides n.
If:
$n \bmod i = 0$
then i is a factor.
4. When a small factor is found, decrement k.
Since we are iterating upward, these factors are already in ascending order.
5. If k == 0, return i.
This means the current small factor is the kth factor overall.
6. Compute the paired factor:
$\frac{n}{i}$
If this paired factor is different from i, append it to larger_factors.
This avoids double counting perfect square roots.
7. After the loop finishes, process larger_factors in reverse order.
Reversing restores ascending order for the larger half of the factors.
8. For each reversed larger factor, decrement k.
If k == 0, return the current factor.
9. If all factors are exhausted and k is still positive, return -1.
This means n has fewer than k factors.
Why it works
Every factor of n belongs to exactly one factor pair:
$(i, \frac{n}{i})$
By iterating only up to the square root, we discover every pair exactly once.
Small factors appear in ascending order during the forward iteration. Large factors appear in descending order, so reversing them restores ascending order.
Because the algorithm visits every factor exactly once in sorted order, decrementing k correctly identifies the kth factor.
Python Solution
class Solution:
def kthFactor(self, n: int, k: int) -> int:
larger_factors = []
i = 1
while i * i <= n:
if n % i == 0:
k -= 1
if k == 0:
return i
paired_factor = n // i
if paired_factor != i:
larger_factors.append(paired_factor)
i += 1
for factor in reversed(larger_factors):
k -= 1
if k == 0:
return factor
return -1
The implementation begins by creating larger_factors, which stores the larger divisor from each factor pair.
The while loop iterates only while:
$i^2 \leq n$
This is equivalent to iterating up to the square root of n.
Whenever i divides n, we immediately count it as a valid factor by decrementing k.
If k reaches zero, we return i because the smaller factors are already encountered in ascending order.
Next, we compute the paired factor using integer division:
paired_factor = n // i
If the paired factor differs from i, we append it to larger_factors. This condition prevents double counting perfect square roots.
After the loop, the larger factors exist in descending order. Reversing them restores ascending order, allowing us to continue counting factors correctly.
If we exhaust all factors without reaching the kth one, we return -1.
Go Solution
func kthFactor(n int, k int) int {
largerFactors := []int{}
for i := 1; i*i <= n; i++ {
if n%i == 0 {
k--
if k == 0 {
return i
}
pairedFactor := n / i
if pairedFactor != i {
largerFactors = append(largerFactors, pairedFactor)
}
}
}
for i := len(largerFactors) - 1; i >= 0; i-- {
k--
if k == 0 {
return largerFactors[i]
}
}
return -1
}
The Go implementation follows the same logic as the Python solution.
Slices are used instead of Python lists for storing larger factors. Reverse traversal is done manually using an index loop because Go does not provide a built in reverse iterator.
Integer arithmetic is straightforward because the problem constraints are small, so overflow is not a concern.
Worked Examples
Example 1
Input: n = 12, k = 3
Factors of 12:
[1, 2, 3, 4, 6, 12]
Iteration Trace
| i | Is Factor? | k After Decrement | larger_factors | Action |
|---|---|---|---|---|
| 1 | Yes | 2 | [12] | continue |
| 2 | Yes | 1 | [12, 6] | continue |
| 3 | Yes | 0 | [12, 6, 4] | return 3 |
Answer:
3
Example 2
Input: n = 7, k = 2
Factors of 7:
[1, 7]
Iteration Trace
| i | Is Factor? | k After Decrement | larger_factors | Action |
|---|---|---|---|---|
| 1 | Yes | 1 | [7] | continue |
| 2 | No | 1 | [7] | continue |
Now process reversed larger_factors:
| Factor | k After Decrement | Action |
|---|---|---|
| 7 | 0 | return 7 |
Answer:
7
Example 3
Input: n = 4, k = 4
Factors of 4:
[1, 2, 4]
Iteration Trace
| i | Is Factor? | k After Decrement | larger_factors | Action |
|---|---|---|---|---|
| 1 | Yes | 3 | [4] | continue |
| 2 | Yes | 2 | [4] | continue |
Notice that 2 is not added twice because:
paired_factor == i
Process reversed larger_factors:
| Factor | k After Decrement | Action |
|---|---|---|
| 4 | 1 | continue |
No more factors remain, so return -1.
Answer:
-1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(sqrt(n)) | We iterate only up to the square root of n |
| Space | O(sqrt(n)) | Larger paired factors may be stored |
The square root optimization is possible because factors always appear in complementary pairs. Instead of scanning every number from 1 to n, we only inspect candidates up to the square root and reconstruct the remaining factors from the stored pairs.
The auxiliary space comes from storing larger factors. In the worst case, approximately half of the divisors discovered before the square root are stored.
Test Cases
solution = Solution()
assert solution.kthFactor(12, 3) == 3 # standard composite number
assert solution.kthFactor(7, 2) == 7 # prime number
assert solution.kthFactor(4, 4) == -1 # k exceeds number of factors
assert solution.kthFactor(1, 1) == 1 # smallest possible n
assert solution.kthFactor(1, 2) == -1 # only one factor exists
assert solution.kthFactor(16, 3) == 4 # perfect square
assert solution.kthFactor(16, 5) == 16 # last factor of perfect square
assert solution.kthFactor(24, 6) == 8 # middle factor in larger set
assert solution.kthFactor(13, 1) == 1 # first factor always 1
assert solution.kthFactor(13, 3) == -1 # prime has only two factors
assert solution.kthFactor(1000, 1) == 1 # large boundary value
assert solution.kthFactor(1000, 16) == 1000 # last factor
| Test | Why |
|---|---|
n=12, k=3 |
Basic composite example |
n=7, k=2 |
Prime number handling |
n=4, k=4 |
k larger than factor count |
n=1, k=1 |
Minimum input boundary |
n=1, k=2 |
Single factor edge case |
n=16, k=3 |
Perfect square handling |
n=16, k=5 |
Final factor in perfect square |
n=24, k=6 |
Multiple factor pairs |
n=13, k=1 |
First factor case |
n=13, k=3 |
Prime number overflow case |
n=1000, k=1 |
Upper bound input |
n=1000, k=16 |
Large factor list traversal |
Edge Cases
One important edge case occurs when n = 1. The number 1 has exactly one factor, itself. Many implementations accidentally assume at least two factors exist because most positive integers have both 1 and n as separate divisors. This implementation handles the case correctly because the loop processes i = 1, immediately decrements k, and returns 1 when appropriate.
Another critical edge case involves perfect squares such as 16 or 25. In these cases, the square root appears as both members of the factor pair:
$4 \times 4 = 16$
A naive factor pair implementation may accidentally count the square root twice. The condition:
if paired_factor != i:
prevents duplicate insertion and guarantees the factor list remains correct.
A third important edge case occurs when k is larger than the total number of factors. For example:
n = 4, k = 4
Since 4 only has three factors, the algorithm must return -1. The implementation naturally handles this by exhausting both the small factor scan and the reversed larger factor list without ever reducing k to zero.
A final subtle case involves prime numbers. Prime numbers have exactly two factors:
1 and n
The algorithm correctly identifies this because only 1 divides evenly before the square root. The paired factor n is stored and later returned if k == 2. Any larger k correctly returns -1.