{x}
blog image

The kth Factor of n

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?

Problem: 1492. The kth Factor of n

This problem asks to find the k-th factor of a given integer n. Factors are integers that divide n without leaving a remainder. The factors should be returned in ascending order. If n has fewer than k factors, return -1.

Solution Approaches and Code

Two solutions are presented below: a brute-force approach and an optimized approach.

Solution 1: Brute Force Enumeration

This approach iterates through all numbers from 1 to n, checking if each number is a factor of n. If it is, we decrement k. When k becomes 0, we've found the k-th factor.

Time Complexity: O(n) - We iterate through all numbers up to n. Space Complexity: O(1) - Constant extra space is used.

Code (Python3):

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

Code (Java):

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

(Similar implementations can be easily written in C++, Go, TypeScript, and other languages following the same logic)

Solution 2: Optimized Enumeration

This approach leverages the property that factors come in pairs. If x is a factor of n, then n/x is also a factor. We iterate only up to the square root of n. For each factor found, we decrement k. If k reaches 0, we've found the k-th factor. If k is still greater than 0 after iterating up to the square root, we iterate downwards from the square root, finding the remaining factors in descending order until k reaches 0.

Time Complexity: O(√n) - We iterate up to the square root of n. Space Complexity: O(1) - Constant extra space is used.

Code (Python3):

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

Code (Java):

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

(Similar implementations for C++, Go, and TypeScript would follow the same optimized logic)

The optimized solution provides a significant improvement in performance for larger values of n, as its time complexity is significantly better than the brute-force approach. Choose the solution that best fits your needs based on the expected input size and performance requirements.