# The kth Factor of n Leetcode Solution

Difficulty Level Medium
MathViews 2192

## Problem Statement

The kth Factor of n Leetcode Solution: states that 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 `k`th 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:

The factor list is [1, 7], and the 2nd factor is 7.

## Example 3:

Input:

n = 4, k = 4

Output:

-1

Explanation:

The factors list is [1, 2, 4], and there are only 3 factors. We should return -1.

## Approach

### Idea:

Suppose we are given a number n, we will run a loop from 1 to n.

For each iteration, we will check if n%i==0 i.e n is divisible by i. At the same time, we will increase the count variable.

If count equals k for certain i, then we have found the kth factor of n, and we will return i.

If no such kth factor of n is found, then return -1. In the worst case, the loop runs till n, Hence O(n) is the worst-case time complexity.

## Code

### The kth Factor of n Leetcode C++ Solution:

```class Solution {
public:
int kthFactor(int n, int k) {
int count=0;
for(int i=1;i<=n;i++)
{
if(n%i==0)count++;
if(count==k)return i;
}
return -1;
}
};```

### The kth Factor of n Leetcode Java Solution:

```class Solution {
public int kthFactor(int n, int k) {
int count = 0;
for(int i=1;i<=n;i++){
if(n%i==0){
count++;
}
if(count==k){
return i;
}
}
return -1;
}
}```

### The kth Factor of n Leetcode Python Solution:

```class Solution:
def kthFactor(self, n: int, k: int) -> int:
count = 0
for i in range(1, n + 1):
if math.fmod(n, i)==0:
count += 1
if count == k:
return i
return -1```

## Complexity Analysis for the kth Factor of n LeetCode Solution:

### Time Complexity

The time complexity of the above code is O(n). We start finding factors from 1 to n and in the worst case, it iterates till n. Hence, the worst-case time complexity is O(n).

### Space Complexity

The space complexity of the above code is O(1) since we aren’t using any extra space here.

Translate »