Problem

You are 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 thekth factor in this list or return -1 if n has less than k factors.

Examples

Example 1

1
2
3

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Example 2

1
2
3

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.

Example 3

1
2
3

Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.

Constraints

  • 1 <= k <= n <= 1000

Follow up:

Could you solve this problem in less than O(n) complexity?

Solution

Method 1 - Brute Force (O(n))

Loop from 1 to n, collect all factors, and return the kth if it exists.

Code

1
2
3
4
5
6
7
8
9

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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
    }
}
1
2
3
4
5
6
7

def kthFactor(n: int, k: int) -> int:
    for i in range(1, n+1):
        if n % i == 0:
            k -= 1
            if k == 0:
                return i
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

pub fn kth_factor(n: i32, k: i32) -> i32 {
    let (mut count, mut k) = (0, k);
    for i in 1..=n {
        if n % i == 0 {
            k -= 1;
            if k == 0 {
                return i;
            }
        }
    }
    -1
}
1
2
3
4
5
6
7
8
9

function kthFactor(n: number, k: number): number {
    for (let i = 1; i <= n; ++i) {
        if (n % i === 0) {
            --k;
            if (k === 0) return i;
        }
    }
    return -1;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)