# The kth Factor of n
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-kth-factor-of-n)
Canonical: https://scaleengineer.com/dsa/problems/the-kth-factor-of-n
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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?

# Approaches
## Brute Force Iteration
This approach involves a straightforward linear scan through all numbers from 1 to `n`. For each number, we check if it's a factor of `n`. We use a counter to keep track of how many factors we've found. When the counter reaches `k`, we've found our target and can return the current number.
**Time:** O(n). In the worst-case scenario, we might have to iterate through all numbers from 1 to `n` to find the k-th factor or to determine that it doesn't exist. · **Space:** O(1). We only use a few variables to store the counter and the loop index, regardless of the size of `n`.
**Pros:** Very simple to understand and implement.; Requires minimal memory (constant space complexity).
**Cons:** The time complexity is linear with respect to `n`, which can be slow if `n` is very large. For the given constraints (`n <= 1000`), it's acceptable, but it doesn't scale well.
### Explanation
The brute-force algorithm is the most intuitive way to solve this problem. We simply iterate through all possible candidates for factors, which are the integers from 1 up to `n`.

We maintain a counter, initialized to zero. As we iterate, if we find a number `i` that divides `n` evenly (`n % i == 0`), we've found a factor. Since we are iterating in ascending order, the first factor we find is the 1st factor, the second is the 2nd, and so on. We increment our counter for each factor found. As soon as our counter equals `k`, we have located the k-th factor and can return it. If we iterate through all numbers up to `n` and the counter never reaches `k`, it means `n` has fewer than `k` factors, and we should return -1 as per the problem description.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate with a loop variable `i` from `1` to `n`.
- Inside the loop, check if `i` is a factor of `n` using the modulo operator (`n % i == 0`).
- If `i` is a factor, increment `count`.
- If `count` becomes equal to `k`, it means `i` is the k-th factor. Return `i` immediately.
- If the loop completes without the `count` reaching `k`, it implies that `n` has fewer than `k` factors. In this case, return `-1`.

## Optimized Approach using Square Root
A more efficient approach leverages a mathematical property of factors. If `i` is a factor of `n`, then `n / i` is also a factor. This allows us to find all factors by iterating only up to the square root of `n`, which significantly improves performance, especially for large `n`.
**Time:** O(sqrt(n)). The main loop runs from 1 up to the square root of `n`. Operations inside the loop, like list appends, take amortized constant time. · **Space:** O(sqrt(n)). In the worst case, we might store up to `2*sqrt(n)` factors. For example, for a highly composite number. The space used is proportional to the number of factors, which is bounded by `O(sqrt(n))`.
**Pros:** Significantly faster than the O(n) approach, with a time complexity of O(sqrt(n)).; This is a standard and efficient technique for problems involving factors of a number.
**Cons:** Requires extra space to store the factors, proportional to the number of factors, which can be up to `O(sqrt(n))`.; The logic is slightly more complex than the brute-force approach, involving two lists and index manipulation.
### Explanation
This optimized method is based on the observation that factors of a number `n` come in pairs. If `i` is a factor, then `n/i` is also a factor. One of these factors will be less than or equal to `sqrt(n)`, and the other will be greater than or equal to `sqrt(n)`. The only exception is when `n` is a perfect square, in which case `sqrt(n)` is a factor, and its pair is itself.

We can iterate from `i = 1` to `sqrt(n)`. For every `i` that divides `n`, we find a small factor `i` and a large factor `n/i`. We can store these in two separate lists. The list of small factors will naturally be sorted in ascending order. The list of large factors will be generated in descending order.

The complete sorted list of factors is the concatenation of the `smallFactors` list and the reversed `largeFactors` list. To find the k-th factor, we first check if it falls within the `smallFactors` list. If it does, we return it directly. If not, we calculate its position within the `largeFactors` list and return the appropriate element.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int kthFactor(int n, int k) {
        List<Integer> smallFactors = new ArrayList<>();
        List<Integer> largeFactors = new ArrayList<>();
        
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                smallFactors.add(i);
                if (i * i != n) {
                    largeFactors.add(n / i);
                }
            }
        }
        
        if (k <= smallFactors.size()) {
            return smallFactors.get(k - 1);
        }
        
        int totalFactors = smallFactors.size() + largeFactors.size();
        if (k > totalFactors) {
            return -1;
        }
        
        // The k-th factor is in the largeFactors list.
        // largeFactors are stored in descending order.
        // We need the (k - smallFactors.size())-th element from the sorted large factors.
        int largeFactorIndex = k - smallFactors.size();
        return largeFactors.get(largeFactors.size() - largeFactorIndex);
    }
}
```
### Algorithm
- Create two lists: `smallFactors` and `largeFactors`.
- Iterate `i` from `1` up to `floor(sqrt(n))`.
- If `n` is divisible by `i`:
    - Add `i` to `smallFactors`.
    - If `i*i != n` (to handle perfect squares correctly), add the corresponding larger factor `n/i` to `largeFactors`.
- After the loop, we have two lists. `smallFactors` is sorted ascendingly, and `largeFactors` is sorted descendingly.
- If `k <= smallFactors.size()`, the answer is the `(k-1)`-th element of `smallFactors`.
- Otherwise, the answer is in `largeFactors`. First, check if `k` is out of bounds (`k > smallFactors.size() + largeFactors.size()`). If so, return -1.
- The target is the `(k - smallFactors.size())`-th element from the group of large factors (when sorted). Since our `largeFactors` list is in descending order, we retrieve the element at index `largeFactors.size() - (k - smallFactors.size())`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int kthFactor(int n, int k) {
    int i = 1;
    for (; i < n / i; ++i) {
      if (n % i == 0 && (--k == 0)) {
        return i;
      }
    }
    if (i * i != n) {
      --i;
    }
    for (; i > 0; --i) {
      if (n % (n / i) == 0 && (--k == 0)) {
        return n / i;
      }
    }
    return -1;
  }
};

```

### Python

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

```