Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript
• Java 2
• C++ 2
• Python 2
• Go 2
• TypeScript 2

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

• 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
  
  

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

• function kthFactor(n: number, k: number): number {
      for (let 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;
      }
  }
  

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

• 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
  
  

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

• function kthFactor(n: number, k: number): number {
      let i: number = 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 % Math.floor(n / i) === 0 && --k === 0) {
              return Math.floor(n / i);
          }
      }
      return -1;
  }
  
  

All Problems

All Solutions