Others
This is just a math problem. It’s good to try brute force. It might be enough to get an answer. If not, find something of math rules.
You are given two positive integers
n
and k. A factor of an integer
nis defined as an integer
iwhere
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
ifn
has less thank
factors.Constraints:
1 <= k <= n <= 1000
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.
Upper limit of this problem is not high.
Brute force is enough to solve the problem.
There’s no need to check more than half of the given number, so the loop ends at n // 2 + 1
.
In the end, k is still 1, n is the answer.
Otherwise, return -1.
class TheKThFactorOfN:
def kthFactor(self, n: int, k: int) -> int:
for x in range(1, n // 2 + 1):
if n % x == 0:
k -= 1
if k == 0:
return x
return n if k == 1 else -1
O(n)
O(1)