# 1492. The kth Factor of n

## Naive

T: O(n)

S: O(n)

```java
class Solution {
    public int kthFactor(int n, int k) {
        List<Integer> factor = new ArrayList<>();
        for (int i = 1 ; i <= n; i++) {
            if (n % i == 0) {
                factor.add(i);
            }
        }
        return factor.size() < k ? -1 : factor.get(k-1);
    }
}
```

## Naive with early return

because we only want kth factor, so if we find it, we return it immediately

T: O(n)

S: O(k)

```java
class Solution {
    public int kthFactor(int n, int k) {
        List<Integer> factor = new ArrayList<>();
        for (int i = 1 ; i <= n; i++) {
            if (n % i == 0) {
                factor.add(i);
            }
            if (factor.size() == k) {
                return i;
            }
        }
        return -1;
    }
}
```

## Naive with k--

but actually we don't need to store the factor

T: O(n)

S: O(1)

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

T: O(sqrt(n)

S: O(1)

```java
class Solution {
    public int kthFactor(int n, int k) {
        int sqrt = (int)Math.sqrt(n);
        for (int i = 1; i <= sqrt; i++) {
            if (n % i == 0 && --k == 0) { // use --k, -- first
                return i;
            }
        }
        
        if (sqrt*sqrt == n) {
            sqrt--;
        }
        
        for (int i = sqrt; i >= 1; i--) {
            if (n % i == 0 && --k == 0) {
                return n/i;
            }
        }
        return -1;
    }
}
/*


do sqrt(n) why?

because you'll find factors are paired
-> [1, 2, 3, 4, 6, 12]

1*12
2*6
3*4

so if we find x, we can find another one is n/x. ex:  x = 2, another one is 12/2 = 6. -> paired!

so first for loop ( 1 to sqrt(12) )
i = 1 to sqrt(12) => 1 to 3   
exam 1, 2, 3 is find kth? 

if not find keep do second part ( start from sqrt(12) to 1)  why reversely?
so 3 to 1
12/3 = 4
12/2 = 6
12/1 = 12
in this way we also can find kth in order

2. edge case is perfect sqrt, so 

if (sqrt*sqrt == n) {
    sqrt--;
}
why?

ex: n = 9
[1,3,9]

in this way first loop is 1 to <= 3,  k = 3-2 =1

 sqrt--; => sqrt => 3-- = 2
 
 from 2 to 1
 
 so only 1 can fit 9%1 == 0, so return 9/1 = 9
 
 
 or easy way is in first loop, dont use == sqrt -> then in first loop just 1 to < 3 => 1 to 2. so only 1 fit, k - 1 => k = 2
 
 the  in second loop 3 to 1, so 3 and 1 fit, so k-=2 => find ans is 9/1 = 9

*/
```

```
 or easy way is in first loop, dont use == sqrt -> then in first loop just 1 to < 3 => 1 to 2. so only 1 fit, k - 1 => k = 2
 
 the  in second loop 3 to 1, so 3 and 1 fit, so k-=2 => find ans is 9/1 = 9
```

but I think this one is tricky, because don't know why, i < sqrt -> here need use double type sqrt...

or it's wrong....

```java
class Solution {
    public int kthFactor(int n, int k) {
        double sqrt = Math.sqrt(n);
        for (int i = 1; i < sqrt; i++) {
            if (n % i == 0 && --k == 0) { // use --k, -- first
                return i;
            }
        }
        
        for (int i = (int)sqrt; i >= 1; i--) {
            if (n % (n/i) == 0 && --k == 0) {
                return n/i;
            }
        }
        return -1;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/math/1492.-the-kth-factor-of-n.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.