1492. The kth Factor of n - Detailed Explanation

Problem Statement

Given two positive integers n and k, a factor of n is a positive integer that divides n evenly (i.e. without leaving a remainder). The task is to find the kth factor of n when the factors are listed in ascending order. If n has fewer than k factors, return -1.

Example 1

• Input: n = 12, k = 3
• Explanation:
  The factors of 12 are: [1, 2, 3, 4, 6, 12].
  The 3rd factor is 3.
• Output: 3

Example 2

• Input: n = 7, k = 2
• Explanation:
  The factors of 7 are: [1, 7].
  The 2nd factor is 7.
• Output: 7

Example 3

• Input: n = 4, k = 4
• Explanation:
  The factors of 4 are: [1, 2, 4].
  There is no 4th factor.
• Output: -1

Constraints

• 1 ≤ n ≤ 1000
• 1 ≤ k ≤ n

Hints to Guide Your Approach

1. Understand the Factor Definition:
   A factor divides the number evenly, so for any integer i, if n % i == 0, then i is a factor of n.

2. Order Matters:
   Factors are considered in ascending order. You could either iterate from 1 to n and count each factor or collect them (perhaps using a √n optimization) and sort them.

3. Optimizations:
   Although you could simply loop from 1 to n, you can reduce the number of iterations by noticing that factors come in pairs (if i is a factor, so is n/i). Be cautious to keep them in sorted order.

Approaches to Solve the Problem

Approach 1: Simple Iteration (Brute Force)

Explanation

• Idea:
  Loop from 1 through n. Each time you find a divisor (i.e. n % i == 0), count it. When the count reaches k, return that number.

• Steps:

  1. Initialize a counter.
  2. For each integer i from 1 to n, check if i divides n evenly.
  3. Increment the counter for every factor found.
  4. When the counter equals k, return i.
  5. If you complete the loop without reaching k, return -1.

• Complexity Analysis:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Approach 2: Optimized Iteration Using √n

Explanation

• Idea:
  Every factor i of n has a corresponding factor n/i. You can iterate only up to √n and collect factors in two lists—one for factors found directly (in ascending order) and one for their paired factors (which will be in descending order). Then, merge the lists carefully to get the complete sorted order.

• Steps:

  1. Initialize two lists: one for small factors (from 1 to √n) and one for their corresponding large factors.

  2. Iterate i from 1 to √n.

     • If n % i == 0, add i to the small factors list.
     • If i is not equal to n/i (to avoid duplicates, especially when n is a perfect square), add n/i to the large factors list.

  3. Reverse the large factors list (since it will be in descending order).

  4. Concatenate the small factors list with the reversed large factors list.

  5. Check if the total number of factors is at least k; if yes, return the kth factor (1-indexed), otherwise return -1.

• Complexity Analysis:

  • Time Complexity: O(√n + f log f) where f is the number of factors (but f is small compared to n)

  • Space Complexity: O(f), which is acceptable since the number of factors is low.

Code Implementations

Python Code

Below is the Python implementation using the simple iteration approach. (The √n approach can be implemented similarly.)