The kth Factor of n

Math, Number Theory

Original Link

Solution

In this problem, we should find all factors that meet n % i == 0. Before getting all possible factors, we are unsure if there is a kth number. The easy solution is to check all possible numbers if n is divisible by that number. The input size is too small, so we can solve this problem with O(N) time complexity.

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

However, this solution won’t pass if the size of N becomes large. To make it more effective, we should consider the divisor's aspect. When a number X can divide the number N, then we know that N/X is also the divisor of N. For example, if we know that 3 is the divisor of 15, 5 is also the divisor of 15 automatically.

Then, we don’t need to check all numbers smaller than N. We only need to check until ceil(sqrt(N)). It’s because that sqrt(N) * sqrt(N) = N. If the previous sqrt(N) is larger, the later sqrt(N) should be smaller. It was already checked before we checked sqrt(N).

class Solution {
public:
    int kthFactor(int n, int k) {
        vector<int> ans;
        for (int i = 1; i * i <= n; ++i) {
            if (n % i == 0) ans.push_back(i);
            if (n % i == 0 && i != n / i) ans.push_back(n/i);
        }
        sort(ans.begin(), ans.end());
        k--;
        return ans.size() > k ? ans[k] : -1;
    }
};