Code Implementation

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        count = 0
        for i in range(1, n+1):
            if n % i == 0:
                count += 1
                if count == k:
                    return i
        return -1
      

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

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

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

Problem Description

Given two positive integers n and k, you are asked to find the kth smallest factor of n. A factor of n is defined as an integer i such that n % i == 0 (i.e., i divides n exactly). Factors are considered in increasing order. If n has fewer than k factors, return -1.

• Each factor must be unique; do not reuse elements.
• There is no guarantee that n has at least k factors.
• Return -1 if the kth factor does not exist.

Thought Process

The problem asks for the kth factor of n in ascending order. The most straightforward way to approach this is to check every integer from 1 to n and collect those that divide n without a remainder. We can count these factors as we go, and when we reach the kth one, we return it.

However, iterating through all numbers up to n can be slow for large n. To optimize, we can observe that factors come in pairs: if i is a factor, then n / i is also a factor. This allows us to only check up to the square root of n and build the list of factors more efficiently.

The main idea is to balance simplicity (brute-force) and efficiency (using factor pairs), depending on the problem constraints.

Solution Approach

• Step 1: Iterate from 1 to n
  For each integer i in this range, check if n % i == 0. If so, i is a factor.
• Step 2: Count factors
  Maintain a counter to keep track of how many factors we've found. Each time we find a factor, increment the counter.
• Step 3: Return the kth factor
  If the counter reaches k, return the current factor i immediately.
• Step 4: Handle missing kth factor
  If the loop completes and we haven't found k factors, return -1.

This approach is easy to implement and understand. For further optimization, one could collect all factors up to the square root of n, sort them, and assemble the full list of factors in order, but for most constraints, the above method is sufficient.

Example Walkthrough

Let's walk through the process with n = 12 and k = 3:

1. i = 1: 12 % 1 == 0, so 1 is a factor. (count = 1)
2. i = 2: 12 % 2 == 0, so 2 is a factor. (count = 2)
3. i = 3: 12 % 3 == 0, so 3 is a factor. (count = 3)

Since we've found the 3rd factor at i = 3, we return 3 as the answer.

If k = 6, the process would continue:

4. i = 4: 12 % 4 == 0, so 4 is a factor. (count = 4)
5. i = 6: 12 % 6 == 0, so 6 is a factor. (count = 5)
6. i = 12: 12 % 12 == 0, so 12 is a factor. (count = 6)

The 6th factor is 12.

If k = 7, we would finish the loop without finding a 7th factor, so we return -1.

Time and Space Complexity

• Brute-force approach:
  Time Complexity: O(n), since we may need to check every number from 1 to n.
  Space Complexity: O(1), as we only use a counter and do not store the factors.
• Optimized approach (using factor pairs):
  Time Complexity: O(√n), as we only need to check up to the square root of n and can find factor pairs.
  Space Complexity: O(√n), if we store the list of factors for sorting and combining.

The brute-force method is simple and often fast enough for small to moderate values of n. For very large n, the optimized approach is preferred.

Summary

The problem asks us to find the kth smallest factor of n. The direct solution checks each number up to n and counts factors until the kth is found, which is easy to implement and understand. For larger values of n, optimization via factor pairs can reduce the number of checks. The key insight is that factors always come in pairs, and we only need to count them in order. This makes the solution both efficient and elegant for a wide range of input sizes.