Efficient Algorithms to Compute The kth Factor of a Natural Number N

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.

Example 4:
Input: n = 1, k = 1
Output: 1
Explanation: Factors list is [1], the 1st factor is 1.

Example 5:
Input: n = 1000, k = 3
Output: 4
Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].

Constraints:
1 <= k <= n <= 1000

Hints:
The factors of n will be always in the range [1, n].
Keep a list of all factors sorted. Loop i from 1 to n and add i if n % i == 0. Return the kth factor if it exist in this list.

O(N) Bruteforce Algorithm to Compute The kth Factor of N

Let’s try from 1 to N and check if it is divisible. Return the Kth factor if exists:

1
2
3
4
5
6
7
8
9
10
11
12

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

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

We can optimise the solution to O(N/2) as apparently there are no factor between number N/2+1 to N-1.

1
2
3
4
5
6
7
8
9
10
11
12

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

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

The solution is still linear but the implementation will be faster than the first version of the bruteforce.

O(Sqrt(N)) Optimised Bruteforce Algorithm to Compute The kth Factor of N

We know for every factor d, there will be a pair factor n/d except when d*d == n. Thus, we have to only check from 1 to Sqrt(N), and take care of the specical case when d*d==N. Two loops of O(Sqrt(N)). First iterate from 1 to Sqrt(N), and then downwards to 1 i.e. n/i.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int kthFactor(int n, int k) {
        int d = 1;
        for (; d * d <= n; ++ d) {
            if (n % d == 0) {
                if (-- k == 0) {
                    return d;
                }
            }
        }
        for (d = d - 1; d >= 1; -- d) {
            if (d * d == n) continue;
            if (n % d == 0) {
                if (-- k == 0) {
                    return n / d;
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    int kthFactor(int n, int k) {
        int d = 1;
        for (; d * d <= n; ++ d) {
            if (n % d == 0) {
                if (-- k == 0) {
                    return d;
                }
            }
        }
        for (d = d - 1; d >= 1; -- d) {
            if (d * d == n) continue;
            if (n % d == 0) {
                if (-- k == 0) {
                    return n / d;
                }
            }
        }
        return -1;
    }
};

The algorithm complexity is O(Sqrt(N)).

–EOF (The Ultimate Computing & Technology Blog) —