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.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — The kth Factor of n — problem

0. Pattern family

Family: Number theory / factors enumeration

1. Why / judgment (K3)

k-th smallest divisor of n. Enumerate factors in O(√n): walk i=1..√n, collect small and large factors; merge sorted. Early exit if k-th found in ascending scan.

2. Worked complexity / derivation (K11)

O(√n) time, O(√n) space for factor list (or O(1) extra with two-pass count).
Trial division to n is O(n) — fine for tiny n, worse teaching.

3. Pattern + recognition + when-NOT (K12)

Name: FACTOR SCAN O(√n)

Recognition: k-th divisor; n up to 1e9 → must √n not O(n).

When-NOT: Prime factorization for product of many queries → sieve/precompute. k-th prime → different.

4. Edge hand-run (K13)

n=12 k=3 → factors 1,2,3,4,6,12 → 3. k=5 →6. k=7 → -1. n=1 k=1 →1. n=7 k=2 →7.

5. Interviewer follow-ups & drills

Q1. Why pair i and n/i?
Model answer: Factors come in pairs; careful when i*i==n double-count.

Q2. Sorted order without sort?
Model answer: Collect lows ascending then highs reverse.

Q3. n=1e12?
Model answer: Still √n ~1e6 ok; beyond may need pollard in contest — not here.

✅ Solution 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

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.
Iterate through potential factors: Loop through numbers i starting from 1 up to n inclusive. Each i represents a potential factor of n.
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.
Increment the factor counter: If i is a factor of n (i.e., the condition in step 3 is true), increment factorCount by 1.
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.
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

java

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 .

🎯 STRICT STANDOUT — Solution The kth Factor of n

0. Pattern family

Family: O(√n) factor listing

1. Why / judgment (K3)

Loop i from 1 to √n; if n%i==0 record i and n/i (if distinct). Sort or two-list merge; return k-th or -1. Interview variant: count without storing then second pass.

2. Worked complexity / derivation (K11)

Θ(√n) iterations. Sorting factors O(√n log √n) negligible. Space O(number of factors) ≤ O(√n).

3. Pattern + recognition + when-NOT (K12)

Name: DIVISOR ENUMERATION

Recognition: k-th divisor queries.

When-NOT: All primes ≤n sieve. Factorize then DFS generate all divisors for highly composite offline.

4. Edge hand-run (K13)

n=12 → [1,2,3,4,6,12]; k=3→3; k=6→12; k=7→-1. Perfect square n=9: factors 1,3,9 — don't double 3.

5. Interviewer follow-ups & drills

Q1. Square root double-count?
Model answer: if i != n/i push both; if equal once.

Q2. k=1 always?
Model answer: 1 is always a factor.

Q3. Prime n?
Model answer: factors [1,n]; k=2→n; k=3→-1.

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on The kth Factor of n? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **The kth Factor of n** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **The kth Factor of n** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **The kth Factor of n**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **The kth Factor of n**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Combinations Minimizing Array After Replacing P →