The Kth Factor Of N - Leetcode Solution

Problem Statement:

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:

Input: n = 12, k = 3 Output: 3 Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Solution Approach:

Let's start by generating all factors of n using a for loop that goes from 1 to n. For each i in the loop, we check if n % i == 0, which means that i is a factor of n. If we find a factor, we append it to a list.

To return the kth factor, we can simply return the k-1th element of the list if it exists, else return -1.

Here is the implementation of the above approach:

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        factors = []
        for i in range(1, n+1):
            if n % i == 0:
                factors.append(i)
        return factors[k-1] if len(factors) >= k else -1

Time Complexity: The for loop goes from 1 to n, so the time complexity is O(n).

Space Complexity: We use a list to store all factors, so the space complexity is O(n).

Overall, the above solution provides a brute-force approach to solve the problem. It performs well for smaller values of n, but can be optimized to improve performance for larger values of n.

1