Question

1492. The kth Factor of n

中文文档

Description

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 _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.

 

Constraints:

• 1 <= k <= n <= 1000

 

Follow up:

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

Solutions

Solution 1

class Solution:
  def kthFactor(self, 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

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

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

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

Solution 2

class Solution:
  def kthFactor(self, n: int, k: int) -> int:
    i = 1
    while i * i < n:
      if n % i == 0:
        k -= 1
        if k == 0:
          return i
      i += 1
    if i * i != n:
      i -= 1
    while i:
      if (n % (n // i)) == 0:
        k -= 1
        if k == 0:
          return n // i
      i -= 1
    return -1

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

func kthFactor(n int, k int) int {
  i := 1
  for ; i < n/i; i++ {
    if n%i == 0 {
      k--
      if k == 0 {
        return i
      }
    }
  }
  if i*i != n {
    i--
  }
  for ; i > 0; i-- {
    if n%(n/i) == 0 {
      k--
      if k == 0 {
        return n / i
      }
    }
  }
  return -1
}