Domain 2MediumMEDIUM

The kth Factor of n

Find the kth smallest factor of n by iterating up to sqrt(n) and collecting divisor pairs, then sorting.

Domain: medium•Updated: 2026-09-17
#Math#Array#O(sqrt(n))#Sorting

Problem Breakdown

We are given two positive integers n and k. Our goal is to identify the kth smallest factor (divisor) of n. If n has fewer than k factors, we must return -1.

Inputs:

  • n: A positive integer (1≤n1 \le n).
  • k: An index representing which factor in ascending order to retrieve.

Outputs:

  • The specific integer that is the kth factor, or -1 if it doesn’t exist.

Implicit Constraints & Edge Cases:

  • Small Inputs: n=1n=1. Since 1 has only one factor (itself), k must be 1 here; otherwise return -1.
  • Perfect Squares: If i×i=ni \times i = n, we shouldn’t count the square root twice in our list of factors.
  • Scalability: While constraints say n≤1000n \le 1000 (where a linear scan works), FAANG interviews expect solutions that scale to larger inputs (n≈109n \approx 10^9). A solution iterating up to n is technically correct for the given constraint but suboptimal. We should aim for n\sqrt{n}.
  • Indexing: Factors are 1-indexed in problem description (kth), so we need to adjust array indices accordingly (factors[k-1]).

Intuition

A naive approach would be to iterate from i = 1 up to n, checking if n % i == 0. We maintain a counter and return the current i when it hits k. Brute Force Complexity: O(n)O(n). For large inputs (e.g., 10910^9), this will time out.

Key Insight: Factors come in pairs (i,n/i)(i, n/i) where their product is n. One factor must be ≤n\le \sqrt{n} and the other ≥n\ge \sqrt{n}. By iterating only up to int(sqrt(n)), we can find all unique factors much faster (O(n)O(\sqrt{n})). We collect these candidates. Since finding them in order isn’t guaranteed (the large pair n/in/i is found while processing small ii, but appears larger), the most robust way during an interview—unless asked for space optimization—is to store valid pairs and sort, or handle the logic carefully. Given that the number of factors is relatively small compared to sqrt(n), sorting a list of candidates is negligible overhead.

Approach

  1. Initialize an empty list to hold found factors.
  2. Iterate integer i from 1 up to and including int(sqrt(n)).
  3. If n % i == 0:
    • Add i (the small factor) to our list.
    • Check if it’s a perfect square (i * i != n). If not, add the corresponding large pair n // i as well. This ensures we capture all factors without duplicates for squares.
  4. Sort the collected list of factors in ascending order (since small and large pairs are mixed during discovery).
  5. Check if k is within bounds (len(factors)). If not, return -1. Otherwise, return factors[k-1].

Complexity Analysis

Time Complexity: O(n+d(n)log⁡(d(n)))O(\sqrt{n} + d(n) \log(d(n))), where d(n)d(n) is the number of divisors. The loop runs n\sqrt{n} times to find factors. Sorting takes negligible time because d(n)d(n) grows much slower than any polynomial (max factors for n=109n=10^9 is 1344). Effectively, this simplifies to O(n)O(\sqrt{n})” in practice compared to the naive O(n)O(n). Space Complexity: O(d(n))O(d(n)), where we store all divisors. Since d(n)d(n) is small (logarithmic relative to n), space usage is minimal.

Solution

import math

def kthFactor(n: int, k: int) -> int:
    """
    Returns the k-th factor of n in ascending order or -1 if it doesn't exist.
    
    Args:
        n (int): The number to find factors for.
        k (int): The 1-based index of the desired factor.
        
    Returns:
        int: The kth factor or -1.
    """
    # Collect all valid divisors by iterating up to sqrt(n)
    factors = []
    
    limit = math.isqrt(n) 
    
    for i in range(1, limit + 1):
        if n % i == 0:
            factors.append(i)
            # Add the paired factor (n // i), unless it's a perfect square duplicate
            if i * i != n:
                factors.append(n // i)
    
    # Sort to ensure ascending order as required by problem statement
    factors.sort()
    
    # Check bounds and return result or -1
    if k > len(factors):
        return -1
    
    return factors[k-1]

# Example usage:
print(kthFactor(12, 3))   # Output: 3

Edge Cases Handled

  • n = 1, k = 1: The loop runs once for i=1. Factors list becomes [1]. Returns factors[0] which is 1. Correct.
  • Perfect Squares (e.g., n = 4): When i * i == n, we only append the square root to avoid duplicates in our factor count logic before sorting. The sort handles ordering correctly regardless of insertion order.
  • Insufficient Factors: If loop finishes and total factors < k, the length check returns -1.
  • Large Primes (e.g., n = 7): Loop runs up to 7≈2\sqrt{7} \approx 2. Finds factor 1, adds pair 7. List [1, 7]. Returns correct index.