1492. The kth Factor of n
Description
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?
Solutions
Solution 1: Brute Force Enumeration
A "factor" is a number that can divide another number. Therefore, we only need to enumerate from $1$ to $n$, find all numbers that can divide $n$, and then return the $k$-th one.
The time complexity is $O(n)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 |
|
Solution 2: Optimized Enumeration
We can observe that if $n$ has a factor $x$, then $n$ must also have a factor $n/x$.
Therefore, we first need to enumerate $[1,2,...\left \lfloor \sqrt{n} \right \rfloor]$, find all numbers that can divide $n$. If we find the $k$-th factor, then we can return it directly. If we do not find the $k$-th factor, then we need to enumerate $[\left \lfloor \sqrt{n} \right \rfloor ,..1]$ in reverse order, and find the $k$-th factor.
The time complexity is $O(\sqrt{n})$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|