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 ().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: . Since 1 has only one factor (itself),
kmust be 1 here; otherwise return -1. - Perfect Squares: If , we shouldn’t count the square root twice in our list of factors.
- Scalability: While constraints say (where a linear scan works), FAANG interviews expect solutions that scale to larger inputs (). A solution iterating up to
nis technically correct for the given constraint but suboptimal. We should aim for . - 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: . For large inputs (e.g., ), this will time out.
Key Insight: Factors come in pairs where their product is n. One factor must be and the other .
By iterating only up to int(sqrt(n)), we can find all unique factors much faster (). We collect these candidates. Since finding them in order isn’t guaranteed (the large pair is found while processing small , 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
- Initialize an empty list to hold found factors.
- Iterate integer
ifrom1up to and includingint(sqrt(n)). - 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 pairn // ias well. This ensures we capture all factors without duplicates for squares.
- Add
- Sort the collected list of factors in ascending order (since small and large pairs are mixed during discovery).
- Check if
kis within bounds (len(factors)). If not, return-1. Otherwise, returnfactors[k-1].
Complexity Analysis
Time Complexity: , where is the number of divisors. The loop runs times to find factors. Sorting takes negligible time because grows much slower than any polynomial (max factors for is 1344). Effectively, this simplifies to ” in practice compared to the naive .
Space Complexity: , where we store all divisors. Since 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 fori=1. Factors list becomes[1]. Returnsfactors[0]which is1. Correct.- Perfect Squares (e.g.,
n = 4): Wheni * 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 . Finds factor1, adds pair7. List[1, 7]. Returns correct index.