medium The kth Factor of n

Problem Statement

Given two integers, n and k, return the kth smallest factor of n. If n has fewer factors than k factors, return -1.

A factor of a number is an integer that can divide that number without leaving a remainder.

Examples

• Example 1:

  • Input: n = 12, k = 5
  • Expected Output: 6
  • Justification: The factors of 12 are 1, 2, 3, 4, 6, and 12. The fifth smallest factor is 6.

• Example 2:

  • Input: n = 17, k = 2
  • Expected Output: 17
  • Justification: The factors of 17 are 1 and 17, since 17 is a prime number. The second smallest factor is 17.

• Example 3:

  • Input: n = 10, k = 5
  • Expected Output: -1
  • Justification: The factors of 10 are 1, 2, and 5. 10 has only 3 factors, so the answer is -1.

Solution

To solve this problem, we will first calculate all the factors of n by iterating through numbers from 1 to n and checking if n is divisible by each of these numbers without a remainder. If a number is a factor, we increase the count of factors found so far. If the current factor is the kth smallest factor, we consider it as the answer.

This method is effective because it guarantees that we examine all potential divisors of n, thereby not missing any factors. Although this method may not be the most efficient for very large numbers due to its linear complexity, it is straightforward and reliable for a wide range of inputs.

Step-by-Step Algorithm

1. Initialize a counter: Start with a variable factorCount set to 0. This counter will keep track of how many factors of n we have found.

2. Iterate through potential factors: Loop through numbers i starting from 1 up to n inclusive. Each i represents a potential factor of n.

3. Check for divisibility: For each i, check if n % i == 0. This checks whether i is a factor of n by seeing if the division leaves no remainder.

4. Increment the factor counter: If i is a factor of n (i.e., the condition in step 3 is true), increment factorCount by 1.

5. Check if the current factor is the kth factor: If factorCount equals k at any point, return i. This means we've found the kth factor of n.

6. Finish the loop without finding the kth factor: If the loop completes and factorCount is less than k, return -1. This indicates that n does not have a kth factor.

Algorithm Walkthrough

Let's consider the Input: n = 12, k = 5

• Step 1: Initialize factorCount to 0.

• Step 2: Start iterating from i = 1 to i = 12 (inclusive).

  • When i = 1, 12 % 1 == 0. Factor found. Increment factorCount to 1.
  • When i = 2, 12 % 2 == 0. Factor found. Increment factorCount to 2.
  • When i = 3, 12 % 3 == 0. Factor found. Increment factorCount to 3.
  • When i = 4, 12 % 4 == 0. Factor found. Increment factorCount to 4.
  • When i = 5, 12 % 5 != 0. No action is taken since 5 is not a factor.
  • When i = 6, 12 % 6 == 0. Factor found. Increment factorCount to 5.

• Step 5: At this point, when i = 6, factorCount equals k (which is 5). This means we've found the 5th factor of 12. Return i, which is 6.

• The algorithm returns 6 as the output, indicating that the 5th smallest factor of 12 is 6.

Code

public class Solution {

  // Method to find the kth factor of n using O(1) space
  public int kthFactor(int n, int k) {
    int factorCount = 0;
    // Iterate through numbers from 1 to n
    for (int i = 1; i <= n; ++i) {
      // Check if i is a factor of n
      if (n % i == 0) {
        factorCount++; // Increment factor count
        // If factorCount equals k, return i as the kth factor
        if (factorCount == k) {
          return i;
        }
      }
    }
    // If we finish the loop without finding the kth factor, return -1
    return -1;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(solution.kthFactor(12, 5)); // Output: 6
    // Example 2
    System.out.println(solution.kthFactor(17, 2)); // Output: 17
    // Example 3
    System.out.println(solution.kthFactor(10, 5)); // Output: -1
  }
}

Complexity Analysis

Time Complexity:

The primary operation in this algorithm involves iterating through all numbers from 1 to n to find all factors of n. This iteration constitutes the bulk of the computational work, leading to a time complexity of O, where n is the input number.

Space Complexity:

The algorithm uses the constant space. So, the space complexity is .