1492. The kth Factor of n

[zeikar]

Problem link

https://leetcode.com/problems/the-kth-factor-of-n/

Problem Summary

n의 약수 중 k번째 작은 수를 찾는 문제

Solution

그냥 모든 약수를 구하고 정렬 후 k번째를 찾으면 된다.

Follow up

정렬해도 O(n) 이하긴 한데 (O(sqrt(n) log sqrt(n))) 정렬 없이 풀 수 있다.
약수 저장 배열을 2개 두면 된다.

약수를 구할 때 d가 약수이면 배열에 d를 넣고 다른 배열은 n/d를 집어넣으면 각 배열은 정렬이 되어있는 상태이고 k번째는 한번에 구할 수 있다.

이렇게 되면 시간복잡도는 O(sqrt(n))

배열에 넣지 않고 k를 빼주면서 하면 공간복잡도를 O(1)까지 가능하긴 하다.

Source Code

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        smallfactors = []
        largefactors = []
        i = 1
        while i*i <= n:
            if n % i == 0:
                smallfactors.append(i)
                if i != n//i:
                    largefactors.append(n//i)
            i += 1

        sl = len(smallfactors)
        ll = len(largefactors)
        if k > sl + ll:
            return -1
        if k > sl:
            return largefactors[-(k - sl)]
        return smallfactors[k - 1]