Skip to content

1492. The kth Factor of n 👍

  • Time: $O(\sqrt{n})$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int kthFactor(int n, int k) {
    // If i is a divisor of n, then n / i is also a divisor of n. So, we can
    // find all the divisors of n by processing the numbers <= sqrt(n).
    int factor = 1;
    int i = 0;  // the i-th factor

    for (; factor * factor < n; ++factor)
      if (n % factor == 0 && ++i == k)
        return factor;

    for (factor = n / factor; factor >= 1; --factor)
      if (n % factor == 0 && ++i == k)
        return n / factor;

    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int kthFactor(int n, int k) {
    // If i is a divisor of n, then n / i is also a divisor of n. So, we can
    // find all the divisors of n by processing the numbers <= sqrt(n).
    int factor = 1;
    int i = 0; // the i-th factor

    for (; factor * factor < n; ++factor)
      if (n % factor == 0 && ++i == k)
        return factor;

    for (factor = n / factor; factor >= 1; --factor)
      if (n % factor == 0 && ++i == k)
        return n / factor;

    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def kthFactor(self, n: int, k: int) -> int:
    # If i is a divisor of n, then n // i is also a divisor of n. So, we can
    # find all the divisors of n by processing the numbers <= sqrt(n).
    factor = 1
    i = 0  # the i-th factor

    while factor < math.isqrt(n):
      if n % factor == 0:
        i += 1
        if i == k:
          return factor
      factor += 1

    factor = n // factor
    while factor >= 1:
      if n % factor == 0:
        i += 1
        if i == k:
          return n // factor
      factor -= 1

    return -1