1492. The kth Factor of n

Naive

T: O(n)

S: O(n)

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)

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)

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)

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....

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;
    }
}